Submission #756144

#	Time	Username	Problem	Language	Result	Execution time	Memory
756144		vjudge1	Jail (JOI22_jail)	C++17	72 / 100	5077 ms	550472 KiB

jail

#include <bits/stdc++.h>

        using namespace std;

        int Q, N, M;
        int st[120005], ed[120005];
        int P[120005][20], D[120005];
        int S[120005], T[120005], C[120005];
        int timer, tin[120005], out[120005];
        vector<int> adj[120005], G[120005];

        void dfs(int v, int p) {
            P[v][0] = p; D[v] = D[p] + 1;
            tin[v] = timer++;
            for(auto u : adj[v]) {
                if(u == p) continue;
                dfs(u, v);
            }
            out[v] = timer - 1;
        }
        int lca(int u, int v) {
            if(D[u] < D[v]) swap(u, v);
            int K = D[u] - D[v];
            for(int l = 0; l < 20; l++)
                if(K & (1 << l)) u = P[u][l];
            if(u == v) return v;
            for(int l = 19; l >= 0; l--)
                if(P[u][l] != P[v][l])
                    u = P[u][l], v = P[v][l];
            return P[u][0];
        }
        bool anc(int a, int b) {
            return (tin[b] >= tin[a] && tin[b] <= out[a]);
        }
        bool intersect(int a, int b, int c) {
            int p = lca(a, b);
            if(c == p) return 1;
            return (anc(c, a) ^ anc(c, b));
        }

        int32_t main() {
            ios_base::sync_with_stdio(0);
            cin.tie(0); cout.tie(0);
            cin >> Q;
            while(Q--) {
                cin >> N; timer = 0;
                for(int l = 0; l < N; l++) {
                    adj[l].clear();
                    st[l] = -1, ed[l] = -1;
                }
                for(int l = 0; l < N - 1; l++) {
                    int U, V; cin >> U >> V; U--; V--;
                    adj[U].push_back(V);
                    adj[V].push_back(U);
                }
                D[1] = -1; dfs(1, 1);
                for(int l = 1; l < 20; l++)
                    for(int i = 0; i < N; i++)
                        P[i][l] = P[P[i][l - 1]][l - 1];
                cin >> M;
                for(int l = 0; l < M; l++) {
                    cin >> S[l] >> T[l]; S[l]--; T[l]--;
                    G[l].clear(), C[l] = 0;
                    st[S[l]] = l, ed[T[l]] = l;
                }
                for(int l = 0; l < M; l++) {
                    int p = lca(S[l], T[l]);
                    vector<int> path, p1;
                    int x = T[l];
                    while(x != p) {
                        p1.push_back(x); x = P[x][0];
                    }
                    reverse(p1.begin(), p1.end()); x = S[l];
                    while(x != p) {
                        path.push_back(x); x = P[x][0];
                    }
                    path.push_back(p);
                    for(auto u : p1) path.push_back(u);
                    for(auto u : path) {
                        if(st[u] != -1 && st[u] != l) G[l].push_back(st[u]), C[st[u]]++;
                        if(ed[u] != -1 && ed[u] != l) G[ed[u]].push_back(l), C[l]++;
                    }
                }
                vector<bool> vis(M, 0); queue<int> q;
                for(int l = 0; l < M; l++)
                    if(C[l] == 0) q.push(l);
                while(!q.empty()) {
                    int a = q.front(); q.pop(); vis[a] = 1;
                    for(auto u : G[a]) {
                        C[u]--; if(C[u] == 0) q.push(u);
                    }
                }
                bool res = 1;
                for(int l = 0; l < M; l++) res &= vis[l];
                cout << (res ? "Yes" : "No") << "\n";
            }
        }

• 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