BOJ 20156 - 기왕 이렇게 된 거 암기왕이 되어라 [C++]

 

문제

https://www.acmicpc.net/problem/20156

 

$i$번 정점의 부모가 $p_i$인 포레스트가 주어지고, 아래와 같은 쿼리가 $M$개 주어진다.

• $x$ : $x$와 $x$의 부모를 잇는 간선이 아직 존재한다면, 끊는다.

 

이 때, 아래와 같은 질의 $K$개를 처리해야 한다.

• $a$ $b$ $c$ : $a$번 쿼리까지 수행되었을 때, $b$와 $c$가 연결되어있는가?

 

풀이

쿼리에 의해 끊어지는 간선들은 모두 끊어놓고 질의를 오프라인으로 처리한다.쿼리를 역순으로 수행하면 간선을 잇는 쿼리로 바뀌며, 각 질의는 분리 집합으로 해결할 수 있게 된다.

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int root[100001]{};
int find(int x){
    if(x == root[x])    return x;
    return root[x] = find(root[x]);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    int N, M, K;
    cin>>N>>M>>K;
    iota(root, root+N+1, 0);

    int par[100001]{};
    for(int i=1;i<=N;i++){
        int a;
        cin>>a;
        par[i] = a;
    }
    vector<int> R(M);
    bitset<100001> chk;
    for(int i=0;i<M;i++){
        int a;
        cin>>a;
        if(chk[a])  continue;
        R[i] = a;
        chk[a] = 1;
    }

    vector<tuple<int, int, int, int>> query;
    for(int i=0;i<K;i++){
        int a,b,c;
        cin>>a>>b>>c;
        query.emplace_back(a,b,c,i);
    }
    sort(query.begin(), query.end(), greater<>());

    for(int i=1;i<=N;i++){
        if(chk[i])  continue;
        if(par[i] == -1)    continue;
        int x = find(i), y = find(par[i]);
        root[x] = y;
    }

    bitset<100001> ans;
    int round = M-1;
    for(auto &[a,b,c,i] : query){
        while(round > a-1){
            int n = R[round];
            round--;
            if(!n)  continue;
            if(par[n] == -1)    continue;
            int x = find(n), y = find(par[n]);
            if(x == y)  continue;
            root[x] = y;
        }
        ans[i] = find(b) == find(c);
    }
    for(int i=0;i<K;i++)    cout<<(ans[i] ? "Same Same;\n" : "No;\n");

}