Submission #1256594

#TimeUsernameProblemLanguageResultExecution timeMemory
1256594PieArmyJail (JOI22_jail)C++20
0 / 100
54 ms104520 KiB
//debugla!!!! #include<bits/stdc++.h> typedef long long ll; #define pb push_back #define fr first #define sc second using namespace std; const int lg=17; int n,m; vector<int>komsu[120023]; int bin[120023][lg]; int dep[120023]; vector<int>dir[120023*(lg+1)*2]; int vis[120023*(lg+1)*2]; pair<int,int>p[120023]; int lca(int a,int b){ if(dep[a]<dep[b])swap(a,b); for(int i=0;i<lg;i++){ if(((dep[a]-dep[b])>>i)&1){ a=bin[a][i]; } } if(a==b)return a; for(int i=lg-1;i>=0;i--){ if(bin[a][i]!=bin[b][i]){ a=bin[a][i]; b=bin[b][i]; } } return bin[a][0]; } void dfs(int pos){ for(int i=1;i<lg;i++){ bin[pos][i]=bin[bin[pos][i-1]][i-1]; } for(int x:komsu[pos]){ if(x==bin[pos][0])continue; bin[x][0]=pos; dep[x]=dep[pos]+1; dfs(x); } } bool dfs2(int pos){ if(pos>=n*(lg+1)*2)return true; //cout<<pos<<" "; vis[pos]=1; for(int x:dir[pos]){ if(vis[x]==2)continue; if(vis[x]==1){ cout<<x<<"*"; return false; } if(!dfs2(x)){ cout<<pos<<" "; return false; } } vis[pos]=2; return true; } void code(){ cin>>n; for(int i=0;i<n;i++){ komsu[i].clear(); } for(int i=0;i<(lg+1)*n*2;i++){ dir[i].clear(); vis[i]=0; } for(int i=1;i<n;i++){ int x,y;cin>>x>>y; x--;y--; komsu[x].pb(y); komsu[y].pb(x); } for(int i=0;i<lg;i++) bin[n][i]=n; bin[0][0]=n; dep[n]=-1; dep[0]=0; dfs(0); cin>>m; for(int i=0;i<m;i++){ cin>>p[i].fr>>p[i].sc; p[i].fr--;p[i].sc--; int lc=lca(p[i].fr,p[i].sc); int a=p[i].fr,b=p[i].sc; int pos=bin[a][0]; dir[b*(lg+1)*2].pb(a*(lg+1)*2+1); for(int j=lg-1;j>=0;j--){ if(dep[bin[pos][j]]>=dep[lc]){ dir[pos*(lg+1)*2+(j+1)*2+1].pb(a*(lg+1)*2+1); pos=bin[bin[pos][j]][0]; } } if(pos==lc){ dir[pos*(lg+1)*2+1].pb(a*(lg+1)*2+1); } pos=b; for(int j=lg-1;j>=0;j--){ if(dep[bin[pos][j]]>dep[lc]){ dir[pos*(lg+1)*2+(j+1)*2+1].pb(a*(lg+1)*2+1); pos=bin[bin[pos][j]][0]; } } if(bin[pos][0]==lc){ dir[pos*(lg+1)*2+1].pb(a*(lg+1)*2+1); } swap(a,b); pos=bin[a][0]; for(int j=lg-1;j>=0;j--){ if(dep[bin[pos][j]]>=dep[lc]){ dir[a*(lg+1)*2].pb(pos*(lg+1)*2+(j+1)*2); pos=bin[bin[pos][j]][0]; } } if(pos==lc){ dir[a*(lg+1)*2].pb(pos*(lg+1)*2); } pos=b; for(int j=lg-1;j>=0;j--){ if(dep[bin[pos][j]]>dep[lc]){ dir[a*(lg+1)*2].pb(pos*(lg+1)*2+(j+1)*2); pos=bin[bin[pos][j]][0]; } } if(bin[pos][0]==lc&&pos!=lc){ dir[a*(lg+1)*2].pb(pos*(lg+1)*2); } } for(int i=0;i<n*(lg+1)*2;i+=2){ int kat=(i>>1)%(lg+1); if(kat==0)continue; int x=(i>>1)/(lg+1); if(kat!=1)x=bin[x][kat-2]; x=bin[x][0]; dir[i-1].pb(i+1); dir[x*(lg+1)*2+(kat-1)*2+1].pb(i+1); dir[i].pb(i-2); dir[i].pb(x*(lg+1)*2+(kat-1)*2); } for(int i=0;i<n*(lg+1)*2;i++){ /*cout<<i<<": "; for(int x:dir[i])cout<<x<<" "; cout<<endl; continue;*/ if(vis[i])continue; if(!dfs2(i)){ cout<<"No"; return; } //cout<<endl; } cout<<"Yes"; } int main(){ ios_base::sync_with_stdio(23-23);cin.tie(0); int q;cin>>q; while(q--){ code();cout<<endl; } }
#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...