Submission #1164965

#TimeUsernameProblemLanguageResultExecution timeMemory
1164965jj_masterJail (JOI22_jail)C++20
0 / 100
1 ms2632 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; vector<int> adj[MAXN]; int depth[MAXN]; int parent[MAXN][20]; int n, m; void dfs(int u, int p) { depth[u] = depth[p] + 1; parent[u][0] = p; for (int i = 1; i < 20; i++) { parent[u][i] = parent[parent[u][i - 1]][i - 1]; } for (int v : adj[u]) { if (v != p) { dfs(v, u); } } } int lca(int u, int v) { if (depth[u] < depth[v]) { swap(u, v); } for (int i = 19; i >= 0; i--) { if (depth[parent[u][i]] >= depth[v]) { u = parent[u][i]; } } if (u == v) { return u; } for (int i = 19; i >= 0; i--) { if (parent[u][i] != parent[v][i]) { u = parent[u][i]; v = parent[v][i]; } } return parent[u][0]; } int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int q; cin >> q; while (q--) { cin >> n; for (int i = 1; i <= n; i++) { adj[i].clear(); depth[i] = 0; for (int j = 0; j < 20; j++) { parent[i][j] = 0; } } for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } dfs(1, 0); cin >> m; vector<int> s(m), t(m); for (int i = 0; i < m; i++) { cin >> s[i] >> t[i]; } vector<int> used(n + 1, 0); bool ok = true; for (int i = 0; i < m; i++) { if (s[i] == t[i]) continue; int d = dist(s[i], t[i]); int u = s[i], v = t[i]; while (d--) { if (used[u]) { ok = false; break; } used[u] = 1; u = parent[u][0]; } if (!ok) break; } cout << (ok ? "Yes" : "No") << '\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...