Submission #546964

#TimeUsernameProblemLanguageResultExecution timeMemory
546964ngraceJail (JOI22_jail)C++14
77 / 100
5086 ms916908 KiB
#include <vector> #include <iostream> #include <utility> #include <set> #include <algorithm> using namespace std; #define v vector #define pii pair<int,int> #define fi first #define se second int N,M; int anc=20; v<v<int>> adj; v<int> depth; v<v<int>> par; v<int> ps; v<int> pe; v<v<int>> num; void dfs(int cur, int from){ if(depth[cur]!=-1) return; depth[cur]=depth[from]+1; par[cur][0]=from; if(ps[cur]!=-1) num[cur][0]++; if(pe[cur]!=-1) num[cur][0]++; for(int it:adj[cur]) dfs(it, cur); } bool is_anc(int cur, int other){ for(int i=anc-1; i>=0; i--){ if(depth[par[cur][i]]>=depth[other]) cur=par[cur][i]; } if(cur==other) return true; return false; } int lca(int a, int b){ if(depth[a]<depth[b]) swap(a,b); for(int i=anc-1; i>=0; i--){ if(depth[par[a][i]]>=depth[b]) a=par[a][i]; } if(a==b) return a; for(int i=anc-1; i>=0; i--){ if(par[a][i]!=par[b][i]){ a=par[a][i]; b=par[b][i]; } } return par[a][0]; } v<set<int>> diadj; v<bool> prevrec; v<bool> vis; bool find_cycle(int cur){ if(!vis[cur]){ vis[cur]=true; prevrec[cur]=true; for(int it:diadj[cur]){ if(!vis[it] && find_cycle(it)){ return true; } else if(prevrec[it]){ return true; } } } prevrec[cur]=false; return false; } int main(){ int Q; cin>>Q; for(int q=0;q<Q;q++){ cin>>N; adj=v<v<int>>(N); bool subone=true; for(int i=0; i<N-1; i++){ int a,b; cin>>a>>b; a--; b--; adj[a].push_back(b); adj[b].push_back(a); if(a+1!=b) subone=false; } if(subone){ cin>>M; v<pii> rooms(M); v<pii> rooms2(M); for(int i=0; i<M; i++){ int a,b; cin>>a>>b; if(b>=a){ rooms.push_back({a,b}); rooms2.push_back({-a,b}); rooms2.push_back({-b,a}); } else{ rooms.push_back({a,-b}); rooms.push_back({b,-a}); rooms2.push_back({-a,-b}); } } sort(rooms.begin(), rooms.end()); sort(rooms2.begin(),rooms2.end()); pii cur={-1,-1}; pii def={-1,-1}; bool out=true; for(pii it:rooms){ if(it.se<=0){ if(cur!=def && cur.se>=it.fi){ out=false; break; } } else{ if(it.se<cur.se){ out=false; break; } cur=it; } } cur={1,1}; def={1,1}; for(pii it:rooms2){ if(it.se>=0){ if(cur!=def && cur.se>=it.fi){ out=false; break; } } else{ if(it.se<cur.se && cur!=def){ out=false; break; } cur=it; } } if(out) cout<<"Yes\n"; else cout<<"No\n"; continue; } cin>>M; v<pii> rooms(M); ps = v<int>(N,-1); pe = v<int>(N,-1); for(int i=0; i<M; i++){ cin>>rooms[i].fi>>rooms[i].se; rooms[i].fi--; rooms[i].se--; ps[rooms[i].fi]=i; pe[rooms[i].se]=i; } depth=v<int>(N,-1); par=v<v<int>>(N,v<int>(anc,-1)); num=v<v<int>>(N,v<int>(anc,0)); dfs(0,0); for(int i=1; i<anc; i++){ for(int j=0; j<N; j++){ par[j][i]=par[par[j][i-1]][i-1]; num[j][i]=num[par[j][i-1]][i-1]+num[j][i-1]; } } bool cycle=false; diadj = v<set<int>>(M); for(int i=0; i<M; i++){ int a=rooms[i].fi; int b=rooms[i].se; int l=lca(a,b); //if have quick way of checking if any are on the path between x and an ancestor of x then can do the while loops below faster with binary lifting while(true){ for(int j=anc-1; j>=0; j--){ if(depth[par[a][j]]<depth[l]) continue; if(num[a][j]==0) a=par[a][j]; } if(ps[a]!=-1 && ps[a]!=i){ diadj[ps[a]].insert(i); if(diadj[i].find(ps[a])!=diadj[i].end()){ cycle=true; break; } } if(pe[a]!=-1 && pe[a]!=i){ diadj[i].insert(pe[a]); if(diadj[pe[a]].find(i)!=diadj[pe[a]].end()){ cycle=true; break; } } if(a==l) break; a=par[a][0]; } if(cycle) break; while(b!=l){ for(int j=anc-1; j>=0; j--){ if(depth[par[b][j]]<=depth[l]) continue; if(num[b][j]==0) b=par[b][j]; } if(ps[b]!=-1 && ps[b]!=i){ diadj[ps[b]].insert(i); if(diadj[i].find(ps[b])!=diadj[i].end()){ cycle=true; break; } } if(pe[b]!=-1 && pe[b]!=i){ diadj[i].insert(pe[b]); if(diadj[pe[b]].find(i)!=diadj[pe[b]].end()){ cycle=true; break; } } b=par[b][0]; } if(cycle) break; } vis = v<bool>(M,false); prevrec = v<bool>(M,false); for(int i=0; i<M; i++){ if(cycle) break; if(!vis[i] && find_cycle(i)){ cycle=true; break; } } if(cycle) cout<<"No\n"; else cout<<"Yes\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...