http://codeforces.com/contest/1131/problem/F


이거


풀이 맞는지좀 봐주셈


일단 유니온 파인드 사용하고(종만북에 구현된거 기준)


예제입력 푸는걸 예시로 들게


1.

일단 유니온파인드는 기본적으로 종만북에 나온것처럼 대표자 배열을 갖고 있음.

그리고 여기에 문제를 풀기위해 새로운 배열을 추가했는데, 초깃값은 자기 자신 하나밖에 담고있지 않는 배열임.

처음 생김새는

[ [1], [2], [3], [4], [5] ]

이렇게 생겼겠지

이걸 이제부터 '나의배열' 이라고 부를게



2.

예를들어서 예제입력에

1 4

가 들어왔다고 치면


둘중 하나를 다른족에 합쳐야 되는데


내경우는 일단 무조건 오른쪽애를 왼쪽에다가 합쳤음.


종만북에서는 rank를 유지하면서 rank가 큰애가 대표자되게 구현했는데


암튼 여기서는 예제입력이 1 4로 됬으면 무조건 4를 1에다가 합침


그래서


find(1)의 '나의배열' 에다가 find(4)의 '나의배열'을 합침.


그럼 나의배열은 이제 이렇게 되겠지


[ [1,4], [2], [3], [4], [5] ]




3.

이런식으로 문제의 예제입력을 처리한다면 '나의배열' 은 아래처럼 변해감


[ [1,4], [2], [3], [4], [5] ]

[ [1,4], [2,5], [3], [4], [5] ]

[ [1,4], [2,5], [3,1,4], [4], [5] ]

[ [1,4], [2,5], [3,1,4,2,5], [4], [5] ]


예제입력끝나고 '나의배열' 에서 제일긴놈을 정답으로 제출함 ( 여기서는 [3,1,4,2,5] )





저거 아이디어 맞음? 물론 N이 15만이라서 파이썬으로는 딱봐도 메모리터지긴 할텐데 C++로 풀어도 저방식 메모리 터짐?


그리고 메모리문제 말고도 '예제입력에서 x y 가 입력되는 순서는 실제 정답에서의 x와 y의 순서와 같다' 라고 가정하고있음. 실제로 위의 예제가 1 4 가 아니라 4 1 로 입력됬다면 또 어떻게 꼬일지 모른다는거임


암튼 이거 푸는방법 아이디어좀... 답지는 읽어봐도 모르겠어 ㅠㅠ


답지에 구현코드는 안나와있고 nlogN 이랑 na(a는 아커만함수) 두가지 방법이 있다는데 nlogN으로 푼다는방식은 읽어도 뭔말인지 모르겠음;;


아커만으로 걸린다는 방식 역시 유니온파인드를 쓴다는거 말고는 뭔말인지 모르겠음;; 해석 plz


이거 '엥? 웰노운아님?' 하면서 푸는애들 신기하다