본문 바로가기

문제

(2)
CERC 2013 Escape, JOISC 2017 Sparklers CERC 2013의 Escape(https://www.acmicpc.net/problem/9539)와 JOISC 2017의 Sparklers(https://oj.uz/problem/view/JOI17_sparklers)를 풀어보자. Escape는 다음과 같은 문제를 풀어야 한다. 트리의 1번 정점에서 시작하여 간선을 따라 움직인다. 처음 체력은 0이다. 각 정점 $i$을 처음으로 방문하면 $H_i$만큼 체력을 얻는다. $H_i0)$의 부모 노드 $u$를 생각하자. $u$의 자식은 $v$만 있다고 생각하자. $H_u0$) 1. 리프 노드: $H_i0$이면 $c_i=0, h_i=H_i$ 2. 여러 자식 체인 합치기 : 이 체인들에서 가능한 많은 체력을 얻어가고 싶다. 따라서 현재 hp $\leq c_i$이면..
특이하게 Union Find하는 문제들 Union Find는 그래프에서 간선이 차례대로 생겨날 때, 두 정점이 같은 component에 있는지 판별하는 쿼리를 $O(logN)$에 해결하는 알고리즘이다. 흔히 사용하는 방법으로는 경로 압축과 랭크 비교가 있다. 이러한 방법으로 Union Find를 하면 component를 깊이가 작은 트리 형태로 관리하게 된다. 그런데 component를 특이한 형태로 관리하면 다른 종류의 쿼리들을 풀 수 있게 된다. 2019 FunctionCup의 갈라파고스 여행(island) (https://oj.uz/problem/view/FXCUP4_island)을 풀어보자. 다음과 같은 쿼리를 해결해야 한다. 간선들에 0 ~ M-1의 번호가 붙여져있는 그래프가 있다. 정점 A[i]에서 정점 B[i]까지 이동할 때, 사..