Submission #867153

#TimeUsernameProblemLanguageResultExecution timeMemory
867153nima_aryanJail (JOI22_jail)C++17
0 / 100
74 ms1164 KiB
/** * author: NimaAryan * created: 2023-10-27 20:13:43 **/ #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "algo/debug.h" #endif using i64 = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int Q; cin >> Q; while (Q--) { int N; cin >> N; vector<vector<int>> t(N); for (int i = 0; i < N - 1; ++i) { int A, B; cin >> A >> B; --A, --B; t[A].push_back(B); t[B].push_back(A); } int M; cin >> M; vector<int> S(M), T(M); vector<int> whoS(N, -1), whoT(N, -1); for (int i = 0; i < M; ++i) { cin >> S[i] >> T[i]; --S[i], --T[i]; whoS[S[i]] = i; whoT[T[i]] = i; } vector up(32, vector<int>(N, -1)); vector<int> par(N), dep(N); /* i -> S(j), i <- T(j) */ vector<vector<int>> d(M); int m = M; auto add_edge = [&](int a, int b) { if (a == m || b == m) { d.emplace_back(); } if (a == -1 || b == -1) { return; } d[a].push_back(b); }; vector fakeS(32, vector<int>(N, -1)); vector fakeT(32, vector<int>(N, -1)); auto dfs = [&](auto self, int v, int p) -> void { par[v] = up[0][v] = p; if (whoS[v] != -1) { fakeS[0][v] = whoS[v]; } if (whoT[v] != -1) { fakeT[0][v] = whoT[v]; } for (int k = 1; k < 32; ++k) { int mid = up[k - 1][v]; if (mid == -1) { break; } up[k][v] = up[k - 1][mid]; add_edge(m, fakeS[k - 1][v]); add_edge(m, fakeS[k - 1][mid]); fakeS[k][v] = m++; add_edge(fakeT[k - 1][v], m); add_edge(fakeT[k - 1][mid], m); fakeT[k][v] = m++; } for (int u : t[v]) { if (u != p) { dep[u] = dep[v] + 1; self(self, u, v); } } }; dfs(dfs, 0, -1); auto jump = [&](int& at, int x) { for (int k = 0; k < 32; ++k) { assert(at != -1); if (x >> k & 1) { at = up[k][at]; } } }; auto LCA = [&](int a, int b) { if (dep[a] < dep[b]) { swap(a, b); } jump(a, dep[a] - dep[b]); if (a == b) { return a; } for (int t = 32 - 1; t >= 0; --t) { int na = up[t][a]; int nb = up[t][b]; if (na != nb) { a = na; b = nb; } } return par[a]; }; for (int i = 0; i < M; ++i) { int lca = LCA(S[i], T[i]); for (int x : {S[i], T[i]}) { if (x == lca) { continue; } x = par[x]; for (int t = 32 - 1; t >= 0; --t) { int y = up[t][x]; if (y != -1 && dep[y] > dep[lca]) { add_edge(i, fakeS[t][x]); add_edge(fakeT[t][x], i); x = y; } } } if (whoS[T[i]] != -1) { add_edge(i, whoS[T[i]]); } if (whoT[S[i]] != -1) { add_edge(whoT[S[i]], i); } } vector<int> vis(m); bool fail = false; auto check = [&](auto self, int v) -> void { vis[v] = 1; for (int u : d[v]) { if (!vis[u]) { self(self, u); } else if (vis[u] == 1) { fail = true; } } vis[v] = 2; }; for (int i = 0; i < m; ++i) { if (!vis[i]) { check(check, i); } } cout << (fail ? "No" : "Yes") << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...