Submission #927348

#TimeUsernameProblemLanguageResultExecution timeMemory
927348andrei_boacaJail (JOI22_jail)C++17
0 / 100
19 ms33884 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; int t,n,m,A[120005],B[120005],in[120005],out[120005],timp,par[120005],niv[1200005],dp[21][120005],nr[120005]; bool isheavy[120005]; vector<int> muchii[120005]; vector<vector<int>> v; vector<set<pii>> suf,active; set<pii> vtm; vector<vector<set<int>>> arb; vector<int> tati; vector<set<int>> emp; int where[120005],poz[120005]; vector<int> stiva; bool use[120005]; bool isancestor(int a,int b) { return in[a]<=in[b]&&out[a]>=out[b]; } int LCA(int a,int b) { if(niv[a]>niv[b]) swap(a,b); if(isancestor(a,b)) return a; for(int i=18;i>=0;i--) if(dp[i][a]!=0&&!isancestor(dp[i][a],b)) a=dp[i][a]; return par[a]; } int dist(int a,int b) { int lca=LCA(a,b); return niv[a]+niv[b]-2*niv[lca]; } void initdfs(int nod) { nr[nod]=1; timp++; in[nod]=timp; dp[0][nod]=par[nod]; for(int i=1;i<=18;i++) dp[i][nod]=dp[i-1][dp[i-1][nod]]; int who=0,maxim=0; for(int i:muchii[nod]) if(i!=par[nod]) { par[i]=nod; niv[i]=niv[nod]+1; initdfs(i); nr[nod]+=nr[i]; if(nr[i]>maxim) { maxim=nr[i]; who=i; } } if(who!=0) isheavy[who]=1; out[nod]=timp; } void buildhld() { for(int i=1;i<=n;i++) { bool ok=1; for(int j:muchii[i]) if(j!=par[i]&&isheavy[j]) { ok=0; break; } if(ok) { vector<int> nodes; int nod=i; while(true) { nodes.push_back(nod); if(!isheavy[nod]) break; nod=par[nod]; } for(int i=0;i<nodes.size();i++) { where[nodes[i]]=v.size(); poz[nodes[i]]=i; } v.push_back(nodes); arb.push_back(emp); suf.push_back(vtm); active.push_back(vtm); int lg=arb.size(); lg--; arb[lg].resize(4*(int)nodes.size()+5); } } } void addnode(int nod,int ind,int add) { int chain=where[nod]; int p=poz[nod]; if(add==1) active[chain].insert({p,ind}); else active[chain].erase({p,ind}); } void update(int chain,int nod,int st,int dr,int a,int b,int val,int add) { if(st>=a&&dr<=b) { if(add==1) arb[chain][nod].insert(val); else arb[chain][nod].erase(val); return; } int mij=(st+dr)/2; if(a<=mij) update(chain,nod*2,st,mij,a,b,val,add); if(b>mij) update(chain,nod*2+1,mij+1,dr,a,b,val,add); } void query(int chain,int nod,int st,int dr,int p) { tati.push_back(nod); if(st==dr) return; int mij=(st+dr)/2; if(p<=mij) query(chain,nod*2,st,mij,p); if(p>mij) query(chain,nod*2+1,mij+1,dr,p); } void addseg(int a,int b,int ind,int add) { int lca=LCA(a,b); while(niv[a]>=niv[lca]) { int p=poz[a]; int chain=where[a]; int last=v[chain].size(); last--; if(where[a]==where[lca]) last=poz[lca]; if(p<=last) { if(last!=(int)v[chain].size()-1) update(chain,1,0,(int)v[chain].size()-1,p,last,ind,add); else { pii x={p,ind}; if(add==1) suf[chain].insert(x); else suf[chain].erase(x); } } a=par[v[chain][last]]; } while(niv[b]>niv[lca]) { int p=poz[b]; int chain=where[b]; int last=v[chain].size(); last--; if(where[b]==where[lca]) last=poz[lca]-1; if(p<=last) { if(last!=(int)v[chain].size()-1) update(chain,1,0,(int)v[chain].size()-1,p,last,ind,add); else { pii x={p,ind}; if(add==1) suf[chain].insert(x); else suf[chain].erase(x); } } b=par[v[chain][last]]; } } void dfs1(int nod) { use[nod]=1; addseg(A[nod],B[nod],nod,-1); addnode(B[nod],nod,-1); int chain=where[A[nod]]; int p=poz[A[nod]]; while(!suf[chain].empty()) { auto it=suf[chain].upper_bound({p,1e9}); if(it==suf[chain].begin()) break; it=prev(it); int x=(*it).second; dfs1(x); } tati.clear(); query(chain,1,0,v[chain].size()-1,p); for(int x:tati) { while(!arb[chain][x].empty()) { int y=*arb[chain][x].begin(); dfs1(y); } } int a=A[nod]; int b=B[nod]; int lca=LCA(a,b); while(a!=0&&niv[a]>=niv[lca]) { p=poz[a]; chain=where[a]; int last=v[chain].size(); last--; if(where[a]==where[lca]) last=poz[lca]; while(!active[chain].empty()) { auto it=active[chain].lower_bound({p,0}); if(it==active[chain].end()) break; if((*it).first>last) break; int x=(*it).second; dfs1(x); } a=par[v[chain][last]]; } while(b!=0&&niv[b]>niv[lca]) { p=poz[b]; chain=where[b]; int last=v[chain].size(); last--; if(where[a]==where[lca]) last=poz[lca]-1; while(!active[chain].empty()) { auto it=active[chain].lower_bound({p,0}); if(it==active[chain].end()) break; if((*it).first>last) break; int x=(*it).second; dfs1(x); } b=par[v[chain][last]]; } stiva.push_back(nod); } void dfs2(int nod) { use[nod]=1; addseg(A[nod],B[nod],nod,-1); addnode(A[nod],nod,-1); int chain=where[B[nod]]; int p=poz[B[nod]]; while(!suf[chain].empty()) { auto it=suf[chain].upper_bound({p,1e9}); if(it==suf[chain].begin()) break; it=prev(it); int x=(*it).second; dfs2(x); } tati.clear(); query(chain,1,0,v[chain].size()-1,p); for(int x:tati) { while(!arb[chain][x].empty()) { int y=*arb[chain][x].begin(); dfs2(y); } } int a=A[nod]; int b=B[nod]; int lca=LCA(a,b); while(a!=0&&niv[a]>=niv[lca]) { p=poz[a]; chain=where[a]; int last=v[chain].size(); last--; if(where[a]==where[lca]) last=poz[lca]; while(!active[chain].empty()) { auto it=active[chain].lower_bound({p,0}); if(it==active[chain].end()) break; if((*it).first>last) break; int x=(*it).second; dfs2(x); } a=par[v[chain][last]]; } while(b!=0&&niv[b]>niv[lca]) { p=poz[b]; chain=where[b]; int last=v[chain].size(); last--; if(where[a]==where[lca]) last=poz[lca]-1; while(!active[chain].empty()) { auto it=active[chain].lower_bound({p,0}); if(it==active[chain].end()) break; if((*it).first>last) break; int x=(*it).second; dfs2(x); } b=par[v[chain][last]]; } } void solve() { cin>>n; timp=0; v.clear(); suf.clear(); active.clear(); arb.clear(); arb.shrink_to_fit(); for(int i=1;i<=n;i++) { muchii[i].clear(); isheavy[i]=0; } for(int i=1;i<n;i++) { int a,b; cin>>a>>b; muchii[a].push_back(b); muchii[b].push_back(a); } niv[1]=1; initdfs(1); cin>>m; for(int i=1;i<=m;i++) cin>>A[i]>>B[i]; buildhld(); stiva.clear(); for(int i=1;i<=m;i++) { addseg(A[i],B[i],i,+1); addnode(B[i],i,+1); } for(int i=1;i<=m;i++) if(!use[i]) dfs1(i); for(int i=0;i<v.size();i++) assert(suf[i].empty()); reverse(stiva.begin(),stiva.end()); for(int i=1;i<=m;i++) { use[i]=0; addseg(A[i],B[i],i,+1); addnode(A[i],i,+1); } int nrcomp=0; for(int i:stiva) if(!use[i]) { nrcomp++; dfs2(i); } if(nrcomp==m) cout<<"Yes\n"; else cout<<"No\n"; /*for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) if(i!=j) { if(onchain(A[j],A[i],B[i])) { edges[j].push_back(i); grad[i]++; } if(onchain(B[j],A[i],B[i])) { edges[i].push_back(j); grad[j]++; } }*/ } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>t; while(t--) solve(); return 0; }

Compilation message (stderr)

jail.cpp: In function 'void buildhld()':
jail.cpp:85:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for(int i=0;i<nodes.size();i++)
      |                         ~^~~~~~~~~~~~~
jail.cpp: In function 'void solve()':
jail.cpp:364:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  364 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
#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...