BOJ 24489 - Farm Updates
간선을 이을 땐 항상 active farm만 가능하다.
DSU류 문제에서 역방향으로 생각하여 끊는 과정을 역으로 이어주며 DSU연산을 활용하는 문제들이 좀 있는데, 이 문제는 특별히 어렵다.
쿼리를 받고 역방향으로 생각한다.
역방향 과정에서 정점 $u$가 relevant되었다면 다시 irrelevant될 수 없음을 관찰한다.
$D$ 의 역과정인 deactivated -> active 가 되었다면 이후로는 쭉 active 일 것이기 때문에 타당하다.
$R$ 의 역과정인 간선을 잇는 과정을 거쳐 relevant가 되었다면 이간선이 $A$로 추가된 시점엔 $u, v$가 active였고, 이로 인해 둘 중 하나가 relevant가 되었다면 둘 다 deactivated된 상태일 수 없기 때문이다.
쿼리를 뒤집고 끝까지 $D$ 가 불리지 않은 간선들을 relevant로 마킹해준다.
$u$가 $D$가 불려 active(relevant)가 되었고 직전까지 irrelevant였다면 $u$와 연결되어있는 것들중 active farm을 통해 이동할 수 있는 것들은 이 시점에 relevant여야 한다.
그런데 active farm을 통해 이동할 수 있는 것들을 검사할 때 지금 irrelevant인 것들로만 이동을 하면 된다.
왜냐면 지금 irrelevant인 것은 deactivate가 이것보다 미리 된 것들이기 때문이다.
이를 DFS로 구현한다.
$u, v$가 $R$이 불려 간선이 추가되었고 둘 중 하나라도 relevant였다면 두개에 대해 동일하게 DFS를 돌려준다.
$A$ 는 신경쓰지 않아도 된다.
Comments