Union-Find Tree (4) 썸네일형 리스트형 [CF] 100551A Connect and Disconnect 문제 링크: https://codeforces.com/gym/100551/problem/A 문제 설명: 정점 $n$개로만 이루어진 그래프에 $k$개의 쿼리가 주어지는데, 쿼리는 +, -, ? 이렇게 세 종류가 있다. +는 존재하지 않는 간선 하나를 추가하고, -는 이미 존재하는 간선 하나를 삭제한다. ?는 현재 그래프의 컴포넌트 개수를 출력한다. $n$과 $k$는 둘 다 30만 이하이다. 문제 풀이: - 쿼리가 오직 + 와 ?만 들어온다면...?Union-Find Tree를 이용해서 정점들을 쉽게 합쳐줄 수 있고, 시간복잡도는 $O(k alpha(k) )$가 되겠다. - 제거 쿼리가 추가되었을 때 만약에 정직하게 모든 쿼리들을 다 처리해 준다면...?Union-Find Tree를 그대로 첫번째 풀이에 적.. [USACO] 2018 January Contest (Silver) 풀이 [15589] Lifeguards (Silver)문제 링크: https://www.acmicpc.net/problem/15589문제 설명: $N$ 마리의 소가 1부터 10억 까지의 단위 시간 사이의 임의의 구간을 덮고 있다. 이 소들 중 한 마리를 제거할 때, 여전히 덮혀 있는 구간의 길이를 최대화 하는 문제이다.문제 풀이: $N$의 범위가 10만밖에 되지 않으므로, 사용하는 좌표 역시 20만개를 초과하지 않는다. 따라서 정렬 및 좌표압축 후 스위핑 비슷하게 단 하나의 소만으로 덮혀 있는 구간과 하나 이상의 소로 덮혀 있는 구간의 길이를 prefix sum으로 계산해 주고, 이를 바탕으로 각 소를 한 번씩 제거해주면서 기존에는 덮혀 있었지만 이제 덮혀지지 않는 구간의 길이를 $O(1)$로 계산해 줄 수 .. [CF] Codeforces Round #464 (Div. 2) 이번 CF는 총 A~F의 6개 문제로 이루어져 있었다. ABCD 50분만에 다풀고 E 하려다가 도저히 못하겠어서 반쯤 던져놓고 있었는데 끝나기 2분 전에 B 해킹이 들어와서 11초 남기고 B번 마지막 서브미션해서 맞았다. 덕분에 점수도 개판되고 레이팅도 100오를거 50밖에 안올랐다. 그래도 D번을 10분만에 풀어내서 점수에 아아주 큰 타격은 안간듯. D번이 이렇게 쉬울 줄 알았으면 DABC 순서로 풀걸 그랬다. 다음은 내가 푼 문제에 대한 솔루션들.A. Love Triangle time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output As you could know .. [BOJ] 13306 트리 문제: https://www.acmicpc.net/problem/13306 2016 KOI 중등부 3번 문제인 트리이다. 고등부 3번과 굉장히 비슷한 문제이기는 한데, 듣기로는 고등부 3번은 HLD라는 알고리즘을 써야 한다고 알고 있는데 이 문제는 상대적으로 깔끔하게 발상의 전환을 통해 문제를 해결할 수 있다. 실제로 대회장에 갔을 때도 모든 풀이는 다 생각해 놨는데 자료구조 구현을 못해서 실패했다. 웬만하면 풀이를 보기 전에 생각을 더 해봤으면 하는 좋은 문제. 내 해법은 Union-Find Tree로 알려져 있는 자료구조 (Disjoint Set)을 구현해서 문제를 역순으로 풀어 나가는 것이다. 어떤 정점과 그 정점의 부모 정점을 제거하면 그 두 트리는 분리되게 된다. 두 정점 사이에 경로가 존재하려.. 이전 1 다음
