백준 17722 - Road Development (C++)

문제

• 문제 링크

  
   BOJ 17722 - Road Development 
  

• 문제 요약

$N$개의 도시로 구성된 국가에 대해, $Q$개의 교통 개선 계획이 주어진다.
$2$번 쿼리가 주어질 때마다 그에 맞는 답을 출력하자.


• 제한

TL : $2$ sec, ML : $256$ MB




$2 ≤ N ≤ 100,000$

$1 ≤ Q ≤ 300,000$

이 문제는 서브태스크 문제이다.

알고리즘 분류

• 자료 구조 (data_structures)
• 트리 (trees)
• heavy-light 분할 (heavy-light decomposition)
• 세그먼트 트리 (segment tree)
• 느리게 갱신되는 세그먼트 트리 (lazy propagation)
• 오프라인 쿼리 (offline_queries)
• 분리 집합 (disjoint_set)

풀이

BOJ 2927 - 남극 탐험 을 풀어 보았다면 크게 어렵지 않은 문제이다.

쿼리를 간단히 요약하자.

$1$ $i$ $j$ : $i$, $j$ 간 이동이 불가능하다면 두 도시를 잇는 도로를 건설한다. 이동이 가능하다면 경로 위 모든 도로를 포장한다.

$2$ $i$ $j$ : 만약 $i$, $j$ 간 교통 개선 계획을 시행했다면 몇 개의 도로를 포장해야 했는지 출력한다.

각 쿼리에서 간단한 유의 사항은 아래와 같다.

$1$번 쿼리에서, 임의의 도로는 최초 한 번만 포장된다.

$2$번 쿼리에서, 만약 $i$, $j$간 이동이 애초에 불가능했다면 $-1$을 출력해야 한다.

---

새로운 도로를 추가하고 말고 하는 등의 쿼리를 온라인 상에서 바로바로 하기엔 다소 무리가 있다.

모든 쿼리를 받아, 주어진 $1$번 쿼리들을 토대로 최종 도시의 모양을 알아내자.

특정 도시 간 이동 가능성 여부는 분리 집합을 통해 쉽게 관리할 수 있다.
이 때의 유의 사항으로 전체 도시가 하나의 트리라는 보장이 없다. 즉, 포레스트를 구성한다고 생각해야 한다.

이제 분리 집합에 사용한 배열을 다시 초기화하고, 최종 도시의 모양을 가진 채 쿼리들을 다시 순회하자.

---

각 경로 상에서, 포장해야 하는 도로의 개수를 $Segment$ $Tree$로 관리하면 $2$번 쿼리는 합 쿼리로 처리할 수 있다.

하지만 트리 위에서 진행해야 하기 때문에, $Heavy$ - $Light$ $Decomposition$ 을 이용해 선형적인 접근을 할 수 있도록 하자.

또한 업데이트 단위가 $Point$가 아닌 $Range$기 때문에 $Lazy$ $Propagation$을 써먹으면 되겠다.
물론 이 과정은 $ETT$ +$LCA$로도 처리가 가능해 보이니, 편한대로 하면 될 듯 하다.

결국 $1$번 쿼리는,

$i$, $j$ 간 이동이 불가능 했다면 단순 경로를 이루는 도로들에 $1$의 가중치를 부여한다.

이동이 가능했다면 단순 경로 상에 기록되어 있는 $1$의 가중치를 $0$으로 바꾼다.

와 같이 처리할 수 있다.

같은 흐름으로 $2$번 쿼리도

$i$, $j$ 간 이동이 불가능 했다면 $-1$을 출력한다.

이동이 가능했다면 단순 경로 상에 합 쿼리를 날린다.

이동 가능성은 앞서 말했 듯 분리 집합을 이용해 쉽게 판단할 수 있다.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
vector <tuple <int, int, int>> Q;
vector <int> seg(1 << 18), lz(1 << 18, -1);
vector <int> edge[N], Gr[N];
 
int par[N], dep[N], top[N], in[N], sz[N];
int n, q, cur, dsu[N];
 
int find(int x) { return dsu[x] = dsu[x] ^ x ? find(dsu[x]) : x; }
void Input()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q; Q.resize(q);
 
    iota(dsu, dsu + N, 0);
    for (auto& [op, i, j] : Q)
    {
        cin >> op >> i >> j;
        if (op & 1)
        {
            int x(find(i)), y(find(j));
            if (x ^ y)
            {
                x > y ? dsu[x] = y : dsu[y] = x;
                edge[i].push_back(j);
                edge[j].push_back(i);
            }
        }
    }
}
void hldInit(int now)
{
    sz[now] = 1;
    for (int& next : edge[now])
        if (!sz[next])
        {
            dep[next] = dep[now] + 1;
            par[next] = now;
            hldInit(next);
            sz[now] += sz[next];
            Gr[now].push_back(next);
 
            if (sz[Gr[now][0]] < sz[next]) swap(Gr[now][0], Gr[now].back());
        }
}
void hldETT(int now)
{
    in[now] = ++cur;
    for (int& next : Gr[now])
    {
        top[next] = next ^ Gr[now][0] ? next : top[now];
        hldETT(next);
    }
}
void propagation(int n, int s, int e)
{
    if (!!~lz[n])
    {
        seg[n] = lz[n] * (e - s + 1);
        if (s ^ e)
            lz[n << 1] = lz[n << 1 | 1] = lz[n];
        lz[n] = -1;
    }
}
int segUpdate(int n, int s, int e, int l, int r)
{
    propagation(n, s, e);
    if (s > r || e < l) return seg[n];
    if (s >= l && e <= r)
    {
        lz[n] = cur;
        propagation(n, s, e);
        return seg[n];
    }
    int m(s + e >> 1);
    return seg[n] = segUpdate(n << 1, s, m, l, r) + segUpdate(n << 1 | 1, m + 1, e, l, r);
}
int segQuery(int n, int s, int e, int l, int r)
{
    propagation(n, s, e);
    if (s > r || e < l) return 0;
    if (s >= l && e <= r) return seg[n];
    int m(s + e >> 1);
    return segQuery(n << 1, s, m, l, r) + segQuery(n << 1 | 1, m + 1, e, l, r);
}
int hldQuery(int op, int x, int y, int res = 0)
{
    auto& f(op & 1 ? segUpdate : segQuery);
    while (top[x] ^ top[y])
    {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res += f(1, 1, n, in[top[x]], in[x]);
        x = par[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return res + f(1, 1, n, in[x] + 1, in[y]);
}
void Query()
{
    iota(dsu, dsu + N, 0);
    for (auto& [op, i, j] : Q)
    {
        int x(find(i)), y(find(j));
        if (op & 1)
        {
            cur = x != y; hldQuery(1, i, j);
            x > y ? dsu[x] = y : dsu[y] = x;
        }
        else
            cout << (x ^ y ? -1 : hldQuery(2, i, j)) << '\n';
    }
}
int main()
{
    Input();
    for (int i(1); i <= n; i++)
        if (!sz[i])
            hldInit(i), hldETT(i);
    Query();
}

comment

끝