Submission #709956

#TimeUsernameProblemLanguageResultExecution timeMemory
709956GrandTiger1729Jail (JOI22_jail)C++17
0 / 100
1 ms212 KiB
#include <iostream> #include <vector> #include <functional> using namespace std; int main(){ cin.tie(0)->sync_with_stdio(0); int t; cin >> t; while (t--){ int n; cin >> n; vector<vector<int>> g(n); for (int i = 0; i < n - 1; i++){ int u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } vector<bool> vis(n); vector<int> dep(n); vector<vector<int>> up(n, vector<int>(__lg(n) + 1)); function<void(int)> dfs = [&](int u){ vis[u] = 1; for (auto &v: g[u]){ if (vis[v]) continue; up[v][0] = u; dep[v] = dep[u] + 1; dfs(v); } vis[u] = 0; }; dfs(0); for (int j = 1; j <= __lg(n); j++){ for (int i = 0; i < n; i++){ up[i][j] = up[up[i][j - 1]][j - 1]; } } auto lca = [&](int u, int v){ if (dep[u] < dep[v]) swap(u, v); for (int i = __lg(n); i >= 0; i--){ if (dep[up[u][i]] >= dep[v]){ u = up[u][i]; } } if (u == v) return u; for (int i = __lg(n); i >= 0; i--){ if (up[u][i] != up[v][i]){ u = up[u][i]; v = up[v][i]; } } return up[u][0]; }; vector<pair<int, int>> tag(n); for (int i = 0; i < n; i++){ tag[i] = make_pair(i, i); } int q; cin >> q; while (q--){ int u, v; cin >> u >> v; u--, v--; int l = lca(u, v); if (dep[l] < dep[tag[u].first]){ tag[u].first = l; } if (dep[l] < dep[tag[v].second]){ tag[v].second = l; } } bool flag = 0; function<void(int)> solve = [&](int u){ vis[u] = 1; pair<int, int> res{u, u}; for (auto &v: g[u]){ if (vis[v]) continue; solve(v); if (dep[tag[v].first] <= dep[u] && dep[tag[v].second] <= dep[u]) flag = 1; if (dep[tag[v].first] <= dep[tag[u].first] || dep[tag[v].second] <= dep[tag[u].second]) flag = 1; if (dep[tag[v].first] <= dep[res.first]) res.first = tag[v].first; if (dep[tag[v].second] <= dep[res.second]) res.second = tag[v].second; } if (dep[res.first] <= dep[tag[u].first]) tag[u].first = res.first; if (dep[res.second] <= dep[tag[u].second]) tag[u].second = res.second; vis[u] = 0; }; solve(0); cout << (!flag? "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...