Submission #1243436

#TimeUsernameProblemLanguageResultExecution timeMemory
1243436AvianshJail (JOI22_jail)C++20
61 / 100
5093 ms46936 KiB
#include <bits/stdc++.h> using namespace std; unordered_set<int>snodes; unordered_set<int>tnodes; unordered_set<int>sfin; unordered_set<int>tfin; void dfs(int st, vector<int>g[], int p, int t, int revs[], int revt[]){ snodes.insert(revs[st]); tnodes.insert(revt[st]); if(st==t){ for(int i : snodes){ sfin.insert(i); } for(int i : tnodes){ tfin.insert(i); } snodes.erase(revs[st]); tnodes.erase(revt[st]); return; } for(int i : g[st]){ if(i==p) continue; if(sfin.size()) break; dfs(i,g,st,t,revs,revt); } snodes.erase(revs[st]); tnodes.erase(revt[st]); } 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]; sfin.clear(); tfin.clear(); for(int i = 0;i<m;i++){ dfs(s[i],g,-1,t[i],revs,revt); for(int j : sfin){ spath[i].insert(j); } for(int j : tfin){ tpath[i].insert(j); } sfin.clear(); tfin.clear(); } 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...