Submission #593018

#	Time	Username	Problem	Language	Result	Execution time	Memory
593018		jhnah917	Jail (JOI22_jail)	C++14	72 / 100	5091 ms	483328 KiB

jail

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

int N, K, P[22][121212], D[121212], C[121212];
vector<int> G[121212], G2[121212];
vector<pair<int,int>> Type[121212];
int In[121212];
void AddEdge(int s, int e){ G2[s].push_back(e); In[e] += 1; }

void Clear(){
    for(int i=1; i<=N; i++) G[i].clear();
    for(int i=1; i<=N; i++) G2[i].clear();
    for(int i=1; i<=N; i++) Type[i].clear();
    fill(In+1, In+N+1, 0);
}

void DFS(int v, int b=-1){
    for(auto i : G[v]) if(i != b) P[0][i] = v, D[i] = D[v] + 1, 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);
    int diff = D[u] - D[v];
    for(int i=0; diff; i++, diff>>=1) if(diff & 1) u = P[i][u];
    if(u == v) return u;
    for(int i=21; i>=0; i--) if(P[i][u] != P[i][v]) u = P[i][u], v = P[i][v];
    return P[0][u];
}

bool OnPath(int u, int v, int x){
    auto check = [&](int up, int dw, int x) -> bool {
        if(D[x] < D[up] || D[dw] < D[x]) return false;
        return Kth(dw, D[dw] - D[x]) == x;
    };
    int l = LCA(u, v);
    return check(l, u, x) || check(l, v, x);
}

bool TopSort(){
    queue<int> Q;
    for(int i=1; i<=K; i++) if(!In[i]) Q.push(i);
    while(!Q.empty()){
        int v = Q.front(); Q.pop();
        for(auto i : G2[v]) if(!--In[i]) Q.push(i);
    }
    return *max_element(In+1, In+N+1) == 0;
}

int S[121212], T[121212];
void Graph5(){
    for(int i=1; i<=K; i++){
        for(int j=1; j<=K; j++){
            if(i == j) continue;
            if(OnPath(S[i], T[i], S[j])) AddEdge(j, i);
            if(OnPath(S[i], T[i], T[j])) AddEdge(i, j);
        }
    }
}

void Graph6(){
    for(int i=1; i<=K; i++){
        Type[S[i]].emplace_back(i, 1);
        Type[T[i]].emplace_back(i, 2);
    }
    for(int i=1; i<=K; i++){
        int a = S[i], b = T[i], l = LCA(a, b);
        for(auto [v,t] : Type[l]){
            if(v == i) continue;
            if(t == 1) AddEdge(v, i);
            if(t == 2) AddEdge(i, v);
        }
        while(a != l){
            for(auto [v,t] : Type[a]){
                if(v == i) continue;
                if(t == 1) AddEdge(v, i);
                if(t == 2) AddEdge(i, v);
            }
            a = P[0][a];
        }
        while(b != l){
            for(auto [v,t] : Type[b]){
                if(v == i) continue;
                if(t == 1) AddEdge(v, i);
                if(t == 2) AddEdge(i, v);
            }
            b = P[0][b];
        }
    }
}

void Solve(){
    cin >> N; Clear();
    for(int i=1,s,e; i<N; i++) cin >> s >> e, G[s].push_back(e), G[e].push_back(s);
    DFS(1);
    for(int i=1; i<22; i++) for(int j=1; j<=N; j++) P[i][j] = P[i-1][P[i-1][j]];

    cin >> K;
    for(int i=1; i<=K; i++) cin >> S[i] >> T[i];
    if(K <= 500) Graph5();
    else Graph6();

    cout << (TopSort() ? "Yes" : "No") << "\n";
}

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

Compilation message (stderr)

jail.cpp: In function 'void Graph6()':
jail.cpp:72:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |         for(auto [v,t] : Type[l]){
      |                  ^
jail.cpp:78:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |             for(auto [v,t] : Type[a]){
      |                      ^
jail.cpp:86:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |             for(auto [v,t] : Type[b]){
      |                      ^

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23