Submission #1243457

#TimeUsernameProblemLanguageResultExecution timeMemory
1243457AvianshJail (JOI22_jail)C++20
72 / 100
4278 ms1114112 KiB
#include <bits/stdc++.h> using namespace std; unordered_set<int>sfin; unordered_set<int>tfin; void dfs(int st, vector<int>g[], int p, int d, int dep[], int par[]){ par[st]=p; dep[st]=d; for(int i : g[st]){ if(i==p) continue; dfs(i,g,st,d+1,dep,par); } } void finder(int s, int t, int revs[], int revt[], int dep[], int par[]){ sfin.clear(); tfin.clear(); while(s!=t){ if(dep[s]<dep[t]){ swap(s,t); } //s is deeper now sfin.insert(revs[s]); tfin.insert(revt[s]); s=par[s]; } sfin.insert(revs[s]); tfin.insert(revt[s]); } bool cyc; void checkcyc(int st, vector<int>g[], int vis[]){ vis[st]=1; for(int i : g[st]){ if(vis[i]==1){ cyc=1; } if(vis[i]) continue; checkcyc(i,g,vis); } vis[st]=2; } void solve(){ int n; cin >> n; vector<int>g[n]; for(int i = 0;i<n-1;i++){ int a,b; cin >> a >> b; a--;b--; g[a].push_back(b); g[b].push_back(a); } int m; cin >> m; int s[m],t[m]; int revs[n],revt[n]; fill(revs,revs+n,-1); fill(revt,revt+n,-1); for(int i = 0;i<m;i++){ cin >> s[i] >> t[i]; s[i]--; t[i]--; revs[s[i]]=i; revt[t[i]]=i; } unordered_set<int>spath[m]; unordered_set<int>tpath[m]; int dep[n]; int par[n]; dfs(0,g,-1,0,dep,par); for(int i = 0;i<m;i++){ finder(s[i],t[i],revs,revt,dep,par); for(int j : sfin){ spath[i].insert(j); } for(int j : tfin){ tpath[i].insert(j); } } vector<int>g2[m]; for(int i = 0;i<m;i++){ for(int j : spath[i]){ if(j==-1||j==i){ continue; } g2[j].push_back(i); } for(int j : tpath[i]){ if(j==-1||j==i){ continue; } g2[i].push_back(j); } } //now check for cycle. cyc=0; int vis[m]; fill(vis,vis+m,0); for(int i = 0;i<m;i++){ if(vis[i]==0){ checkcyc(i,g2,vis); } } for(bool i : vis){ if(!i){ cyc=1; } } if(cyc){ cout << "No\n"; } else{ cout << "Yes\n"; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--){ solve(); } return 0; }
#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...