문제를 간단하게 설명해 드리면 최대 10만개의 노드를가지고 한노드는 최대 5개의 간선을 가질수있고,임의의 노드에서 또다른 임의의 노드로 도달가능합니다. 그리고 3개의 임의의 노드(a,b,c)가 주어집니다. 주어진 3개의 노드에서 주언진 모든 노드까지 거리를 ak bk ck라 할때 임의의 노드 i ,j 에 대해 ai>aj bi>bj ci>cj 이 조건에 해당되는 노드를 찾아 내는 문제입니다.
저는 주어진 임의의노드 3개에서 부터 모든 노드까지 거리를 우선순위 큐를 이용하여 구하고
bk 를 기준으로 오름차순으로 정렬한후 index를 맵핑시킨고 ak기준으로 다시 정렬시킨다음에 구간트리를 이용하여 ak를 기준으로 정렬시킨 순으로 구간트리에 넣었습니다.
구간트리에 넣을때 bk를 구간트리의 구간에 대한 인덱스로 넣어두고 ck를 키값으로 하는 구간트리를 만들었습니다.
그래서 다음 ak수으로 정렬되 노드가 주어지면 앞서서 만들어진 구간트리(구간 1~bk-1) 에서 가장작은 키값을 찾아 ck와 비교하여 작으면 ai>aj bi>bj ci>cj 이조건에 해당되는 노드라고 체크하였습니다.
그러나 이것이 시간초가가 계속 떠서 고생하고 있습니다.
고수님들 도와주세요~~
shinhj88
[체인점][http://www.acmicpc.net/problem/2472]
제가요세 2010년도 정보올림파아드 고등부문제를 풀고있는데
이 알고리즘이 1초에 안에 나올꺼라 생각되는데 풀리 지않아서 도움을 청합니다.
문제를 간단하게 설명해 드리면 최대 10만개의 노드를가지고 한노드는 최대 5개의 간선을 가질수있고,임의의 노드에서 또다른 임의의 노드로 도달가능합니다. 그리고 3개의 임의의 노드(a,b,c)가 주어집니다. 주어진 3개의 노드에서 주언진 모든 노드까지 거리를 ak bk ck라 할때 임의의 노드 i ,j 에 대해 ai>aj bi>bj ci>cj 이 조건에 해당되는 노드를 찾아 내는 문제입니다.
저는 주어진 임의의노드 3개에서 부터 모든 노드까지 거리를 우선순위 큐를 이용하여 구하고
bk 를 기준으로 오름차순으로 정렬한후 index를 맵핑시킨고 ak기준으로 다시 정렬시킨다음에 구간트리를 이용하여 ak를 기준으로 정렬시킨 순으로 구간트리에 넣었습니다.
구간트리에 넣을때 bk를 구간트리의 구간에 대한 인덱스로 넣어두고 ck를 키값으로 하는 구간트리를 만들었습니다.
그래서 다음 ak수으로 정렬되 노드가 주어지면 앞서서 만들어진 구간트리(구간 1~bk-1) 에서 가장작은 키값을 찾아 ck와 비교하여 작으면 ai>aj bi>bj ci>cj 이조건에 해당되는 노드라고 체크하였습니다.
그러나 이것이 시간초가가 계속 떠서 고생하고 있습니다.
고수님들 도와주세요~~
밑에는 제소스를 첨부합니다.
11년 전