https://uva.onlinejudge.org/external/14/1455.pdf
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=30&page=show_problem&problem=2731
타임아웃 떠염!
올해 3월 16일에 풀이 시도했다가 아직도 못푼 문제
whatugo..(sibal214)
2015-11-28 04:21
추천 0
댓글 35
다른 게시글
-
심심하니까 별것도 아닌걸로 싸우네 [7]whatugonna..(sibal214) | 15.11.28추천 0
-
알고리즘 그래프하는대. 내한계가온거같다 [1]misono(211.36) | 15.11.28추천 1
-
ㅅㅅㅅ 아재개그 초고수.. [2]장소삼(223.62) | 15.11.28추천 0
-
파이썬으로 러셀의 역설 문제를 해결하려는데 어렵네!!! [1]두정갑(121.167) | 15.11.28추천 0
-
HTML5로 만든 동영상은 어떻게 퍼가냐? [2]두정갑(121.167) | 15.11.28추천 0
-
맞춤법은 한자 공부하면 많이 좋아진다. [4]ㅅㅅㅅ(175.252) | 15.11.28추천 0
-
스크립트언어 갑은 자바스크립트지 [8]d(125.177) | 15.11.28추천 0
-
자신의 페이스로 살아가자 [5]힘내머리머..(shippuden91) | 15.11.28추천 0
-
c++ 출력 고정 질문 [6]456456(211.225) | 15.11.28추천 0
-
오토핫키로 간단한거 하나 만들려는데 잘안되네요 [1]12342331(121.188) | 15.11.28추천 0
각 도시를 서로 다른 주로 설정
연결할때마다 Union-Find
각 주가 가지는 정보는 대표 도시(임의 지정, union find트리의 루트노드), 최대 최소 horizontal coordinate
그렇게 합치면 해당 주(root)에 연결된 노드 개수 카운트를 요구할때마다 매번 해주게 하나여 아님 매번 root에 뭐 들어올때마다 갯수를 변경해줘서 한번에 뱉나여
아 질문할때 세번째 댓글이 달렸네여
모든 주의 정보(대표도시, 최대, 최소)를 balanced binary tree에 최소 또는 최대를 기준으로 저장하고
그냥 Union-Find 최적화하면 그 트리에 속한 노드 갯수를 저장하게 돼.
이번주는 바쁘고 12월 5일쯤 다시 갤 와서 물어볼게여
계속 이어서, 쿼리 들어오면 bbt에서 검색(최대, 최소 중 뭘로 기준을 잡았는지에 따라 lower/upper bound)하고 기준에 맞는 주를 전부 bbt에서 삭제하고 union find
그리고 결과물 정보를 출력. 물론 빼내면서 주의 갯수, 병합하고난 뒤 도시갯수.
그래.. 나중에 오면 보라고 일단 쓴다.
이거 나름대로 인덱싱도 하고 최적화도 하고 했는데 타임아웃만 떠서 포기했는데.. 친절한 답변 감사해영
쿼리처리하고 병합된 거대주를 다시 bbt에 추가
아니야.. 이런거는 혼자서 하기 힘든 문제가 맞으니까 시도한것도 잘한거야
위에 쓴 알고리즘을 매번 테스트케이스마다 반복하면돼. 물론 초기화 잊지말고.
참고로 구현할때 STL 꼭 써라
bbt는 std set, lower/upper bound는 그대로 stl 함수이름
set 사용법 공부해야겠네영
아 맞다 위에서 좀 잘못쓴거 있는데
쿼리(라인) 처리할때는 병합하지마
병합은 로드에서 하고
그러니까 라인에서는 삭제는 하지말고
bound로 찾은 위치에서 iterator로 순회하면서
임시변수에 도시갯수의 합과 조건에맞는 주의 갯수를 계산하는거지
그리고 고급 문제 편하게 풀려면 stl을 쓰면 좋다. 익혀둬서 나쁠건 없지.
알고리즘 문제 풀때는 컨테이너하고 알고리즘 헤더에 있는 함수만 따로 공부해둬.
벡터나 알고리즘까진 쓰고있었는데 딴건 쓸 기회도 마땅히 없었고 대게 필요한거 만들어 쓰다보니...ㅠ
시간나면 거기에 있는거 직접 간단한 버전으로(템플릿, 클래스 같은거 안써도 되니까) 구현해보면 좋겠네.
크 이 늦은 시간에 잘 배우고 갑니다
만들어 쓰는 것도 나쁘지 않지. 넌 만들면서 공부하고 있는거야.
그래.. 알고리즘 자료구조 공부는 중요하니까 할때 열심히 해둬.
졸업 한학기 남겨두고 휴학한뒤 소멤에서 서티 본다고 급하게 추가 공부하는 중입니다..
구글은 모든 프로그래머의 친구인거 잊지말고..