Submission #1000637

#TimeUsernameProblemLanguageResultExecution timeMemory
1000637onbertJail (JOI22_jail)C++17
100 / 100
1117 ms160592 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 120005, maxN = 480005, lgn = 17, INF = 1e6; int n, m; vector<int> ADJ[maxn], adj[maxn]; pair<int,int> a[maxn]; int sz[maxn], fa[maxn], d[maxn], newid[maxn], lim[maxn], cnter = 0; bool cmp(int &x, int &y) { return sz[x] > sz[y]; } void dfs1(int u) { sz[u] = 1; for (int v:ADJ[u]) { ADJ[v].erase(find(ADJ[v].begin(), ADJ[v].end(), u)); dfs1(v); sz[u] += sz[v]; } sort(ADJ[u].begin(), ADJ[u].end(), cmp); } void dfs2(int u) { cnter++; newid[u] = cnter; for (int v:ADJ[u]) { d[cnter+1] = d[newid[u]] + 1; fa[cnter+1] = newid[u]; dfs2(v); } lim[newid[u]] = cnter; } int skip[maxn]; void dfs3(int u) { for (int v:adj[u]) { if (v == adj[u][0]) skip[v] = skip[u]; else skip[v] = v; dfs3(v); } } vector<pair<int,int>> PATH(int u, int v) { vector<pair<int,int>> path; if (d[u] > d[v]) swap(u, v); path = {{skip[u], u}}; u = skip[u]; while (u>v || v>lim[u]) { u = fa[u]; path.push_back({skip[u], u}); u = skip[u]; } auto [l, r] = path.back(); while (l<r) { int mid = (l+r+1)/2; if (mid<=v && v<=lim[mid]) l = mid; else r = mid-1; } path.back().first = u = l; path.push_back({skip[v], v}); v = skip[v]; while (d[fa[v]] > d[u]) { v = fa[v]; path.push_back({skip[v], v}); v = skip[v]; } path.back().first += d[u] - d[v] + 1; return path; } set<pair<int,int>> chain[maxn]; set<int> seg[maxN]; void build(int id, int l, int r) { seg[id].clear(); if (l==r) return; int mid = (l+r)/2; build(id*2, l, mid); build(id*2+1, mid+1, r); } void update(int id, int l, int r, int &findl, int &findr, int &val, bool psh) { if (r<findl || findr<l) return; if (findl<=l && r<=findr) { if (psh) seg[id].insert(val); else seg[id].erase(val); // if (val == 3) cout << l << " " << r << " " << psh << endl; return; } int mid = (l+r)/2; update(id*2, l, mid, findl, findr, val, psh); update(id*2+1, mid+1, r, findl, findr, val, psh); } void qry(int id, int l, int r, int &target, vector<int> &nxt) { if (r<target || target<l) return; for (int i:seg[id]) nxt.push_back(i); if (l==r) return; int mid = (l+r)/2; qry(id*2, l, mid, target, nxt); qry(id*2+1, mid+1, r, target, nxt); } void UPDATE(int l, int r, int val, int psh) { // if (val == 3) cout << "test " << l << " " << r << " " << psh << endl; if (l==skip[l]) { if (psh) chain[l].insert({r, val}); else chain[l].erase({r, val}); // cout << l << " " << r << " " << val << " " << psh << endl; } else update(1, 1, n, l, r, val, psh); } int S[maxn], vis[maxn]; bool die = false; set<int> exist; void dfs4(int u) { auto [s, t] = a[u]; // cout << "start " << u << " " << s << " " << t << endl; vis[u] = 1; vector<pair<int,int>> path = PATH(s, t); for (auto [L, R]:path) { int cur = L-1; while (true) { cur = *exist.upper_bound(cur); if (cur > R) break; if (cur==s) continue; int v = S[cur]; // cout << "1 " << u << " " << v << " " << die << endl; if (!vis[v]) dfs4(v); else die = true; if (die) return; } } vector<int> nxt; qry(1, 1, n, t, nxt); for (int v:nxt) if (v!=u) { // cout << "2 " << u << " " << v << " " << die << endl; if (!vis[v]) dfs4(v); else if (vis[v]==1) die = true; if (die) return; } int head = skip[t]; pair<int,int> cur = {t, 0}; while (true) { cur = *chain[head].upper_bound(cur); if (cur.first == INF) break; if (cur.second == u) continue; int v = cur.second; // cout << "3 " << u << " " << v << " " << die << endl; if (!vis[v]) dfs4(v); else if (vis[v]==1) die = true; if (die) return; } for (auto [L, R]:path) UPDATE(L, R, u, 0); exist.erase(s); vis[u] = 2; } void solve() { cin >> n; for (int i=1;i<=n;i++) sz[i] = 0, adj[i].clear(), ADJ[i].clear(); cnter = 0; for (int i=1;i<=n-1;i++) { int u, v; cin >> u >> v; ADJ[u].push_back(v); ADJ[v].push_back(u); } fa[1] = 0, d[1] = 0; dfs1(1); dfs2(1); for (int i=1;i<=n;i++) for (int j:ADJ[i]) adj[newid[i]].push_back(newid[j]); skip[1] = 1; dfs3(1); exist = {INF}; build(1, 1, n); for (int i=1;i<=n;i++) chain[i] = {{INF, INF}}, S[i] = -1; cin >> m; for (int i=1;i<=m;i++) { int s, t; cin >> s >> t; s = newid[s], t = newid[t]; a[i] = {s, t}; S[s] = i; exist.insert(s); vector<pair<int,int>> path = PATH(s, t); for (auto [L, R]:path) UPDATE(L, R, i, 1); } for (int i=1;i<=m;i++) vis[i] = 0; die = false; for (int i=1;i<=m;i++) if (!vis[i]) { dfs4(i); if (die) break; } if (die) cout << "No\n"; else cout << "Yes\n"; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) solve(); }
#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...