Submission #648106

#TimeUsernameProblemLanguageResultExecution timeMemory
648106blueJail (JOI22_jail)C++17
100 / 100
1113 ms154352 KiB
#include <iostream> #include <vector> #include <algorithm> #include <set> using namespace std; using vi = vector<int>; using vvi = vector<vi>; using pii = pair<int, int>; using vpii = vector<pii>; const int lg = 17; const int INF = 1'000'000; int N; int M; vi* edge; int ct; vi ord; vi ordind; vvi anc; vi depth; vi subtree; void dfs(int u) { ct++; ord[ct] = u; ordind[u] = ct; for(int v : edge[u]) { if(v == anc[u][0]) continue; anc[v][0] = u; depth[v] = 1 + depth[u]; dfs(v); subtree[u] += subtree[v]; } } int ancestor(int u, int k) { for(int e = 0; e <= lg; e++) if(k & (1 << e)) u = anc[u][e]; return u; } int lca(int u, int v) { if(depth[u] > depth[v]) swap(u, v); v = ancestor(v, depth[v] - depth[u]); if(u == v) return u; for(int e = lg; e >= 0; e--) { if(anc[u][e] == anc[v][e]) continue; u = anc[u][e]; v = anc[v][e]; } return anc[u][0]; } struct segtree1 { vector< set<pii> > markers; vpii bestmark; segtree1() { markers = vector<set<pii>>(1+4*N); bestmark = vector<pii>(1+4*N, {INF, -1}); } void insert(int I, pii V, int i = 1, int l = 1, int r = N) { if(I < l || r < I) return; else if(l == r) { markers[i].insert(V); bestmark[i] = min(bestmark[i], V); } else { insert(I, V, 2*i, l, (l+r)/2); insert(I, V, 2*i+1, (l+r)/2+1, r); bestmark[i] = min({bestmark[i], bestmark[2*i], bestmark[2*i+1]}); } } void erase(int I, pii V, int i = 1, int l = 1, int r = N) { if(I < l || r < I) return; else if(l == r) { markers[i].erase(V); if(markers[i].empty()) bestmark[i] = {INF, -1}; else bestmark[i] = *markers[i].begin(); } else { erase(I, V, 2*i, l, (l+r)/2); erase(I, V, 2*i+1, (l+r)/2+1, r); bestmark[i] = min(bestmark[2*i], bestmark[2*i+1]); } } pii rangemin(int L, int R, int i = 1, int l = 1, int r = N) { if(R < l || r < L) return {INF, -1}; else if(L <= l && r <= R) return bestmark[i]; else return min(rangemin(L, R, 2*i, l, (l+r)/2), rangemin(L, R, 2*i+1, (l+r)/2+1, r)); } }; struct segtree2 { vector<set<pii>> markers; segtree2() { markers = vector<set<pii>>(1+4*N); } void insert(int L, int R, pii V, int i = 1, int l = 1, int r = N) { if(R < l || r < L) return; else if(L <= l && r <= R) { markers[i].insert(V); } else { insert(L, R, V, 2*i, l, (l+r)/2); insert(L, R, V, 2*i+1, (l+r)/2+1, r); } } void erase(int L, int R, pii V, int i = 1, int l = 1, int r = N) { if(R < l || r < L) return; else if(L <= l && r <= R) { markers[i].erase(V); } else { erase(L, R, V, 2*i, l, (l+r)/2); erase(L, R, V, 2*i+1, (l+r)/2+1, r); } } pii pointmax(int I, int i = 1, int l = 1, int r = N) { pii curr = markers[i].empty() ? pii{-INF, -1} : *markers[i].rbegin(); if(l == r) return curr; else if(I <= (l+r)/2) return max(curr, pointmax(I, 2*i, l, (l+r)/2)); else return max(curr, pointmax(I, 2*i+1, (l+r)/2+1, r)); } }; vi S, T; vi A; segtree1 ST1; segtree2 ST2; bool cyclic; void insert_prisoner(int j) { // cerr << "insert prisoner " << j << '\n'; ST1.insert(ordind[S[j]], {depth[A[j]], j}); ST1.insert(ordind[T[j]], {depth[A[j]], j}); ST2.insert(ordind[T[j]], ordind[T[j]] + subtree[T[j]] - 1, {depth[T[j]], j}); } void erase_prisoner(int j) { // cerr << "erase prisoner " << j << '\n'; ST1.erase(ordind[S[j]], {depth[A[j]], j}); ST1.erase(ordind[T[j]], {depth[A[j]], j}); ST2.erase(ordind[T[j]], ordind[T[j]] + subtree[T[j]] - 1, {depth[T[j]], j}); } vi dfsenter; vi dfsexit; void prisonerdfs(int u) { dfsenter[u] = 1; bool usedfirst = 0; bool usedS = 0; erase_prisoner(u); while(1) { pii vp; if(!usedfirst) { // cerr << "type = 1\n"; vp = ST1.rangemin(ordind[S[u]], ordind[S[u]] + subtree[S[u]] - 1); if(vp.first > depth[S[u]]) { usedfirst = 1; // cerr << "continuing\n"; continue; } } else if(!usedS) { // cerr << "type = 2\n"; vp = ST2.pointmax(ordind[S[u]]); if(vp.first < depth[A[u]]) { usedS = 1; // cerr << "continuing\n"; continue; } } else { // cerr << "type = 3\n"; vp = ST2.pointmax(ordind[T[u]]); if(vp.first < depth[A[u]]) { // cerr << "breaking\n"; break; } } int v = vp.second; // cerr << "edge = " << u << " -> " << v << '\n'; if(dfsenter[v] && !dfsexit[v]) { cyclic = 1; return; } else if(dfsenter[v] && dfsexit[v]) { ; } else { insert_prisoner(u); prisonerdfs(v); erase_prisoner(u); if(cyclic) return; } } erase_prisoner(u); dfsexit[u] = 1; } void run() { cin >> N; edge = new vi[1+N]; for(int e = 1; e <= N-1; e++) { int a, b; cin >> a >> b; edge[a].push_back(b); edge[b].push_back(a); } ct = 0; ord = vi(1+N, 0); ordind = vi(1+N, 0); depth = vi(1+N, 0); anc = vvi(1+N, vi(1+lg, 0)); subtree = vi(1+N, 1); anc[1][0] = 0; depth[1] = 1; dfs(1); for(int e = 1; e <= lg; e++) { for(int i = 0; i <= N; i++) { anc[i][e] = anc[ anc[i][e-1] ][e-1]; } } ST1 = segtree1(); ST2 = segtree2(); cyclic = 0; cin >> M; S = T = vi(1+M); A = vi(1+M); for(int j = 1; j <= M; j++) { cin >> S[j] >> T[j]; A[j] = lca(S[j], T[j]); insert_prisoner(j); } dfsenter = dfsexit = vi(1+M, 0); for(int i = 1; i <= M; i++) { if(dfsenter[i]) continue; prisonerdfs(i); if(cyclic) break; } if(cyclic) cout << "No\n"; else cout << "Yes\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int T; cin >> T; for(int t = 1; t <= T; t++) { run(); } cout << "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n"; }
#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...