Submission #646093

#TimeUsernameProblemLanguageResultExecution timeMemory
646093victor_gaoJail (JOI22_jail)C++17
5 / 100
24 ms9696 KiB
//#pragma GCC optimize("Ofast,unroll-loops,O3") //#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native") #include<bits/stdc++.h> //#include<bits/extc++.h> //#pragma pack(1) #define fast ios::sync_with_stdio(0); cin.tie(0); #define int long long #define pii pair<int,int> #define x first #define y second #define N 120015 using namespace std; //using namespace __gnu_pbds; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset; //typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set; int n,m,st[N],ed[N],fa[N],dep[N],dfn[N],dft=0,low[N],nscc=0,lca[N]; int ac[25][N],in[N],out[N],t=0,nxt_start[N],nxt_end[N]; bool ins[N],vis_start[N],vis_end[N]; stack<int>s; pii pos[N]; vector<int>g[N],ng[N],scc[N]; void dfs(int p,int lp,int last_start,int last_end){ nxt_start[p]=last_start; nxt_end[p]=last_end; fa[p]=lp; ac[0][p]=lp; dep[p]=dep[lp]+1; in[p]=++t; int nxt_st=last_start; int nxt_ed=last_end; if (st[p]) nxt_st=st[p]; if (ed[p]) nxt_ed=ed[p]; for (auto i:g[p]){ if (i!=lp) dfs(i,p,nxt_st,nxt_ed); } out[p]=++t; } void build(){ for (int i=1;i<=20;i++){ for (int j=1;j<=n;j++) ac[i][j]=ac[i-1][ac[i-1][j]]; } } bool check(int a,int b){ return in[a]<=in[b]&&out[a]>=out[b]; } int LCA(int a,int b){ if (check(a,b)) return a; else if (check(b,a)) return b; for (int i=20;i>=0;i--){ if (!check(ac[i][a],b)) a=ac[i][a]; } return ac[0][a]; } void tarjan(int p){ dfn[p]=low[p]=++dft; s.push(p); ins[p]=1; for (auto i:ng[p]){ if (!dfn[i]){ tarjan(i); low[p]=min(low[p],low[i]); } else if (ins[i]&&dfn[i]<dfn[p]) low[p]=min(low[p],dfn[i]); } if (low[p]==dfn[p]){ nscc++; for (int x=0;x!=p;s.pop()){ x=s.top(); ins[x]=0; scc[nscc].push_back(x); } } } void find_start(int dx,int di){ vector<pii>vt; vt.push_back({dx,di}); while (!vt.empty()){ int np=vt.back().x; if (!nxt_start[np]) break; else { int ni=nxt_start[np]; int nx=pos[ni].x; while (!vt.empty()){ auto [x,i]=vt.back(); if (dep[lca[i]]>dep[nx]){ vis_start[i]=1; vt.pop_back(); if (!vt.empty()){ // cout<<"add1 : "<<i<<" to "<<vt.back().y<<'\n'; ng[i].push_back(vt.back().y); } } else break; } vt.push_back({nx,ni}); if (vis_start[ni]) break; } } while (!vt.empty()){ auto [x,i]=vt.back(); vis_start[i]=1; vt.pop_back(); if (!vt.empty()){ // cout<<"add2 : "<<i<<" to "<<vt.back().y<<'\n'; ng[i].push_back(vt.back().y); } } } void find_end(int dx,int di){ vector<pii>vt; vt.push_back({dx,di}); while (!vt.empty()){ int np=vt.back().x; if (!nxt_end[np]) break; else { int ni=nxt_end[np]; int nx=pos[ni].y; while (!vt.empty()){ auto [x,i]=vt.back(); // cout<<"Go In "<<lca[i]<<' '<<nx<<" "<<i<<' '<<nx<<'\n'; if (dep[lca[i]]>dep[nx]){ vis_end[i]=1; vt.pop_back(); if (!vt.empty()){ // cout<<"add1 : "<<vt.back().y<<" to "<<i<<'\n'; ng[vt.back().y].push_back(i); } } else break; } vt.push_back({nx,ni}); if (vis_end[ni]) break; } // cout<<di<<" ->\n"; // for (auto i:vt) // cout<<i.x<<' '<<i.y<<"\n"; } while (!vt.empty()){ auto [x,i]=vt.back(); vis_end[i]=1; vt.pop_back(); if (!vt.empty()){ // cout<<"add2 : "<<vt.back().y<<" to "<<i<<'\n'; ng[vt.back().y].push_back(i); } } } void reset(){ while (!s.empty()) s.pop(); dft=0; nscc=0; t=0; for (int i=0;i<=n+5;i++){ st[i]=0; ed[i]=0; fa[i]=0; dep[i]=0; dfn[i]=0; low[i]=0; lca[i]=0; in[i]=0; out[i]=0; nxt_start[i]=0; nxt_end[i]=0; ins[i]=0; vis_start[i]=0; vis_end[i]=0; g[i].clear(); ng[i].clear(); scc[i].clear(); for (int j=0;j<=23;j++) ac[j][i]=0; } } signed main(){ fast int q; cin>>q; while (q--){ reset(); cin>>n; for (int i=1;i<n;i++){ int a,b; cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } cin>>m; for (int i=1;i<=m;i++){ cin>>pos[i].x>>pos[i].y; st[pos[i].x]=i; ed[pos[i].y]=i; } dfs(1,0,0,0); build(); in[0]=0; out[0]=1e18; for (int i=1;i<=m;i++) lca[i]=LCA(pos[i].x,pos[i].y); /* for (int i=1;i<=n;i++) cout<<nxt_start[i]<<" "; cout<<'\n'; for (int i=1;i<=n;i++) cout<<nxt_end[i]<<" "; cout<<'\n'; */ for (int i=1;i<=m;i++){ find_start(pos[i].x,i); find_start(pos[i].y,i); // cout<<i<<" find_start : OK\n"; find_end(pos[i].y,i); find_end(pos[i].x,i); // cout<<i<<" find_end : OK\n"; } for (int i=1;i<=n;i++){ if (st[i]&&ed[i]){ ng[st[i]].push_back(ed[i]); } } /* for (int i=1;i<=m;i++){ cout<<i<<" -> "; for (auto j:ng[i]) cout<<j<<" "; cout<<'\n'; } */ for (int i=1;i<=m;i++){ if (!dfn[i]) tarjan(i); } if (nscc==m) cout<<"Yes\n"; else cout<<"No\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...