백준24942 Jail

작성일 | In

문제 링크

  • https://icpc.me/24942

문제 출처

  • 2021/2022 JOISC Day1 1번

사용 알고리즘

  • 위상 정렬
  • 스파스 테이블

시간복잡도

  • $O(N \log N + M)$

풀이

먼저 선형 구조에서 문제를 해결해 봅시다. 선형 구조에서는 역전이 있으면 불가능하고, 그렇지 않은 경우에는 항상 가능하다는 것을 알 수 있습니다. 또한, 역전이 없을 때는 각 사람을 중간에 멈추지 않고 한 번에 옮길 수 있습니다.
잘 생각해 보면 이 성질은 트리에서도 성립한다는 것을 알 수 있습니다. 즉, $S_i$와 $T_i$를 잇는 경로에 다른 정점 $S_j$ 또는 $T_j$가 없으면 $i$번째 사람을 한 번에 옮길 수 있습니다.

트리 위의 두 경로 $(S_1, T_1)$과 $(S_2, T_2)$를 생각해 봅시다. 만약 경로에 겹치는 부분이 없으면 두 경로의 이동 순서는 상관 없습니다. 또한, 경로의 중간 지점만 겹치는 상황에서도 두 경로의 순서는 상관 없습니다. $S$ 또는 $T$가 다른 경로 위에 놓인 경우만 생각해도 됩니다.
만약 $S_1 - S_2 - T_1$ 경로가 존재하면 $(S_2, T_2)$가 먼저 이동해야 합니다. 반대로 $S_1 - T_2 - T_1$ 경로가 존재하면 $(S_1, T_1)$이 먼저 이동해야 합니다. 정점이 $M$개인 방향 그래프의 위상 정렬로 모델링할 수 있습니다.

단순히 간선을 $O(M^2)$개 생성하면 문제를 해결할 수 없습니다. 하지만 세그먼트 트리를 이용해 그래프의 간선을 줄이는 테크닉과 비슷하게, 스파스 테이블을 이용하면 간선을 $(N \log N + M)$개로 줄일 수 있습니다.

따라서 전체 문제를 $O((N+M) \log N)$ 시간에, $O(1)$ LCA를 사용하면 $O(N \log N + M)$ 시간에 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;

int N, K, V, S[121212], T[121212], SID[121212], TID[121212], D[121212], P[17][121212];
int In[17][121212], Out[17][121212];
vector<int> G[121212];

void Clear(){
    for(int i=1; i<=N; i++) SID[i] = TID[i] = 0, G[i].clear();
    for(int i=0; i<17; i++) memset(P[i], 0, sizeof(int)*(N+1));
}

void DFS(int v, int b=-1){
    for(auto i : G[v]) if(i != b) D[i] = D[v] + 1, P[0][i] = v, DFS(i, v);
}

int Kth(int v, int k){
    for(int i=0; k; i++, k>>=1) if(k & 1) v = P[i][v];
    return v;
}

int LCA(int u, int v){
    if(D[u] < D[v]) swap(u, v);
    u = Kth(u, D[u] - D[v]);
    if(u == v) return u;
    for(int i=16; i>=0; i--) if(P[i][u] != P[i][v]) u = P[i][u], v = P[i][v];
    return P[0][u];
}

void Path(int idx, int v, int len, vector<pair<int,int>> &edges){
    int lg = __lg(len), p = Kth(v, len-(1<<lg));
    edges.emplace_back(In[lg][v], idx);
    edges.emplace_back(idx, Out[lg][v]);
    edges.emplace_back(In[lg][p], idx);
    edges.emplace_back(idx, Out[lg][p]);
}

bool TopoSort(int n, vector<pair<int,int>> edges){
    vector<vector<int>> g(n+1);
    vector<int> in(n+1);
    for(auto [s,e] : edges) g[s].push_back(e), in[e] += 1;
    int cnt = 0;
    queue<int> q;
    for(int i=1; i<=n; i++) if(!in[i]) q.push(i);
    while(!q.empty()){
        int v = q.front(); q.pop(); cnt++;
        for(auto i : g[v]) if(!--in[i]) q.push(i);
    }
    return cnt == n;
}

void Solve(){
    cin >> N;
    for(int i=1,s,e; i<N; i++) cin >> s >> e, G[s].push_back(e), G[e].push_back(s);
    cin >> K;
    for(int i=1; i<=K; i++) cin >> S[i] >> T[i], SID[S[i]] = TID[T[i]] = i;
    DFS(1);
    for(int i=1; i<17; i++) for(int j=1; j<=N; j++) P[i][j] = P[i-1][P[i-1][j]];

    V = K;
    for(int i=0; i<17; i++) for(int j=1; j<=N; j++) In[i][j] = ++V, Out[i][j] = ++V;

    vector<pair<int,int>> E;
    for(int i=1; i<17; i++){
        for(int j=1; j<=N; j++){
            if(D[j] + 1 < (1 << i)) continue;
            E.emplace_back(In[i-1][j], In[i][j]);
            E.emplace_back(In[i-1][P[i-1][j]], In[i][j]);
            E.emplace_back(Out[i][j], Out[i-1][j]);
            E.emplace_back(Out[i][j], Out[i-1][P[i-1][j]]);
        }
    }
    for(int i=1; i<=K; i++) E.emplace_back(i, In[0][S[i]]), E.emplace_back(Out[0][T[i]], i);

    for(int i=1; i<=K; i++){
        int l = LCA(S[i], T[i]);
        for(auto c : {S[i], T[i]}) if(D[c]-D[l]-1 > 0) Path(i, P[0][c], D[c]-D[l]-1, E);
        for(auto c : {S[i], T[i], l}){
            if(SID[c] && SID[c] != i) E.emplace_back(SID[c], i);
            if(TID[c] && TID[c] != i) E.emplace_back(i, TID[c]);
        }
    }
    cout << (TopoSort(V, E) ? "Yes" : "No") << "\n";
    Clear();
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int TC; cin >> TC;
    for(int tc=1; tc<=TC; tc++) Solve();
}