merge tree 이용했는데 기본 이진트리인 merge tree를 쓰니깐 시간초과뜨고....
자식노드만큼 tree를 만들어서 각 노드별로 정점의 부트리를 색깔별로 정렬해놓아서 구하면 메모리 초과뜨고,,,
어떻게 했나요들,,,?
[일반] 2018 UCPC 온라인 예선 1차 F:트리와 색깔 문제 질문!
쿠하하학(202.31)
2018-07-19 13:03
추천 0
댓글 22
다른 게시글
-
정올 하루남았네 ㅋㅋ [3][일반] ㄴ(220.84) | 18.07.19추천 0
-
KOI 대비: (3) 파라메트릭 다지기 [4][문제집] 0xrgb(0xrgb) | 18.07.19추천 14
-
에듀케이셔널 코드포스 솔루션 볼 수 없나요? [4][일반] 제발 도와..(203.253) | 18.07.18추천 0
-
cin cout은 어떻게 해도 scanf printf보다 느린거야? [8][일반] 익명(220.86) | 18.07.18추천 0
-
공지에 있는 코드포스 리커맨더 잘 작동하는거 맞음? [1][일반] 익명(223.62) | 18.07.18추천 0
-
너와 나의 연결 요소 [9][일반] 시아닌(kimjg1119) | 18.07.18추천 0
-
오늘의 문제: 자동차 공장 [5][일반] 0xrgb(0xrgb) | 18.07.18추천 0
-
dp 잘할거면 어떻게 해야하나요?? [7][일반] 하고싶은거..(san9407) | 18.07.17추천 0
-
다들 c++ 포인터 기호랑 참조 기호 띄어쓰기 어떻게 함 [5][일반] 굉굉이(gocabinwood) | 18.07.17추천 0
-
코드포스 말고 대회처럼 하는거 뭐있음? [3][일반] 익명(223.38) | 18.07.17추천 0
Tree를 dfs 순회해서 후위 순서로 번호를 매기면 마치 구간으로 생각할 수 있습니다
이후 Persistent Segement Tree를 이용해서 Online으로 쿼리를 처리하거나, 쿼리를 색깔별로 정렬한 이후 Segment Tree로 오프라인 처리 가능합니다
Tree를 dfs 순회 할때 전위 순서로 매겨도 구간 나오길래 일단 순회는 그렇게 했구요,,,
후자의 방법이면 dfs순회로 만든 배열로 segement Ttree 만들고 query가 k이하 색깔이면 1부터 k까지 순서대로 새그먼트 트리에 넣는다는 얘기인가요?
네
색이 1인걸 모두 넣고, 들어오는 쿼리 중 색깔이 1인걸 먼저 해결하고, 색이 2인걸 모두 넣고, 들어오는 쿼리 처리하고, ...
와 오프라인이라는게 뭐든 쿼리를 저장시킨다음 차례대로 한다는게 오프라인이라는건가요??
혹시 merge Tree를 온라인으로 해결하는거는 시간 초과 날려나요,,?지금 제가 짠게 딱 그렇게 짰는데,,, UCPC 간단한 해걸 방법 2에 그렇게 나와있어서 해봤는데 메모리 초과 뜨더라구요,.,,ㅠㅠ
아 2번 풀이가 그거인가 보네요. 머지트리가 아니고 머지소트 세그먼트트리 인거 같고요
그런데 시간복잡도나 공간복잡도 보면 최적화 안하면 통과 못할수도 있을듯
음 다시 보니까 N이 적어서 문제가 없을거같은데요... 도대체 어떻게 짜신건지
제가 각 노드에맞는 정점의 부트리를 모드 저장하는 식으로 해서 해봤는데 그건 메모리 초과뜨고 머지소트 세그먼트 트리 쓰니깐 메모리 초과는 안뜨는데 시간초과 뜨더라구요,,ㅠㅠ
구간마다 이분탐색을 통해 갯수를 구해서 반환하는 식인데 그렇게 하니깐 시간초과 뜨더라구요,,ㅠㅠ
그건 맞는데 뭔가 다른게 잘못된듯
1. 세그먼트 트리의 노드에는 각 구간에 있는 값들이 merge를 통해 색깔별로 정렬되어 저장되어있음.
2. 온라인으로 처리하는데 쿼리가 들어올 때 마다 구간 찾아서 구간별로 이분탐색을 통해 k이하인 갯수를 파악해서 반환한다.
이건데 왜 시간초과 뜨는지 참..ㅠㅠ
음 일단 맞는거 같아 보이는데
ㅠㅠ 이거 혹시 코드 올릴수도 있나요??
pastebin 같은데 올려서 링크
https://pastebin.com/6X1gSbEu
이렇게 하면 되나여
ㅈㅅ 놋북 업뎃하니까 갑자기 터져서 못볼듯