Submission #544541

#TimeUsernameProblemLanguageResultExecution timeMemory
544541benson1029Jail (JOI22_jail)C++14
100 / 100
2342 ms348616 KiB
#include<bits/stdc++.h> using namespace std; int q, n, m; int timer = 0; int st[120005], ed[120005]; int s[120005], t[120005]; int pst[120005], ped[120005]; vector<int> edg[120005], cyc[4200005]; int lift[120005][17]; int vis[4200005]; bool ans; void dfs(int x, int p) { st[x] = ++timer; lift[x][0] = p; for(int i=1; i<=16; i++) { if(lift[x][i-1]==-1) lift[x][i] = -1; else lift[x][i] = lift[lift[x][i-1]][i-1]; } for(int i:edg[x]) { if(i!=p) dfs(i, x); } ed[x] = ++timer; } bool anc(int x, int y) { return st[x]<=st[y] && ed[x]>=ed[y]; } int lca(int x, int y) { if(anc(x, y)) return x; for(int i=16; i>=0; i--) { if(lift[x][i]==-1) continue; if(!anc(lift[x][i], y)) x = lift[x][i]; } return lift[x][0]; } void dfs2(int x) { // cout << x << " start\n"; vis[x] = 1; for(int i:cyc[x]) { if(vis[i] == 1) { // cout << "gg " << i << "\n"; ans = false; } if(!vis[i]) dfs2(i); } vis[x] = 2; // cout << x << " end\n"; } void solve() { cin >> n; for(int i=1; i<=n; i++) edg[i].clear(); for(int i=1; i<=35*n; i++) cyc[i].clear(); for(int i=1; i<n; i++) { int u,v; cin >> u >> v; edg[u].push_back(v); edg[v].push_back(u); } dfs(1, -1); for(int i=1; i<=n; i++) { for(int j=1; j<=16; j++) { cyc[n*(j+1) + i].push_back(n*(j-1+1) + i); if(lift[i][j-1] != -1) cyc[n*(j+1) + i].push_back(n*(j-1+1) + lift[i][j-1]); cyc[n*(j-1+18) + i].push_back(n*(j+18) + i); if(lift[i][j-1] != -1) cyc[n*(j-1+18) + lift[i][j-1]].push_back(n*(j+18) + i); } } cin >> m; for(int i=1; i<=m; i++) { cin >> s[i] >> t[i]; pst[s[i]] = i; ped[t[i]] = i; } for(int i=1; i<=m; i++) { cyc[i].push_back(n*18 + t[i]); cyc[n*1 + s[i]].push_back(i); cyc[n*18 + s[i]].push_back(i); cyc[i].push_back(n*1 + t[i]); int l = lca(s[i], t[i]); int p = lift[s[i]][0]; if(p!=-1) { if(!anc(p, l)) { for(int j=16; j>=0; j--) { if(lift[p][j]==-1) continue; if(!anc(lift[p][j], l)) { cyc[n*(18+j) + p].push_back(i); cyc[i].push_back(n*(1+j) + p); p = lift[p][j]; } } cyc[n*18 + p].push_back(i); cyc[i].push_back(n*1 + p); } } p = lift[t[i]][0]; if(p!=-1) { if(!anc(p, l)) { for(int j=16; j>=0; j--) { if(lift[p][j]==-1) continue; if(!anc(lift[p][j], l)) { cyc[n*(18+j) + p].push_back(i); cyc[i].push_back(n*(1+j) + p); p = lift[p][j]; } } cyc[n*18 + p].push_back(i); cyc[i].push_back(n*1 + p); } } if(pst[l] != i) cyc[i].push_back(n*1 + l); if(ped[l] != i) cyc[n*18 + l].push_back(i); } for(int i=1; i<=35*n; i++) vis[i] = 0; ans = true; for(int i=1; i<=35*n; i++) { if(!vis[i]) dfs2(i); } cout << (ans ? "Yes\n" : "No\n"); } int main() { ios::sync_with_stdio(false); cin >> q; while(q--) { 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...