Submission #1001162

#TimeUsernameProblemLanguageResultExecution timeMemory
1001162De3b0oJail (JOI22_jail)C++14
0 / 100
6 ms18808 KiB
#include<bits/stdc++.h> #define ll long long #define F first #define S second #define in insert #define pb push_back #define ppb pop_back() #define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define cans cout << ans << "\n"; #define yes cout << "Yes" << "\n"; #define no cout << "No" << "\n"; #define pll pair<ll,ll> #define lin cout << "\n"; #define mod 1000000007 #define mid ((l+r)/2) #define lc (2*x) #define rc (2*x+1) using namespace std; ll n , m; vector<ll> adj[120009]; ll S[120009] , T[120009]; vector<ll> path[120009]; set<ll> pas[120009]; ll pr[120009]; ll o[120009]; vector<ll> g[120009]; ll vs; ll vis[120009]; void ddfs(ll x) { if(vis[x]) return; vis[x]=1; vs++; for(auto it : g[x]) ddfs(it); } void dfs(ll x , ll p , ll f , ll s) { pr[x]=p; if(x==f) { ll y = f; while(y) { path[s].pb(y); pas[s].in(y); y=pr[y]; } reverse(path[s].begin(),path[s].end()); return; } for(auto it : adj[x]) { if(it==p) continue; dfs(it,x,f,s); } } int main() { d3 ll t; cin >> t; while(t--) { cin >> n; for(int i = 1 ; n>=i ; i++) adj[i].clear(); for(int i = 0 ; n-1>i ; i++) { ll u , v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } cin >> m; for(int i = 1 ; m>=i ; i++) { cin >> S[i] >> T[i]; path[i].clear(); pas[i].clear(); dfs(S[i],0,T[i],i); } bool ans = 0; for(int i = 1 ; m>=i ; i++) { for(int j = 1 ; m>=j ; j++) { if(i==j) continue; if(pas[i].find(S[j])==pas[i].end()&&pas[j].find(T[i])==pas[j].end()) { g[j].pb(i); o[i]++; } } } ll x = 0; ll v[120009] = {0}; while(true) { ll y = 0; vector<ll> d; for(int i = 1 ; m>=i ; i++) { if(v[i]) continue; if(o[i]==m-x-1) { v[i]=1; d.pb(i); y++; } } if(!y) break; x+=y; for(auto it : d) { for(auto it1 : g[it]) o[it1]--; } } if(x==m) yes else no } }

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:90:14: warning: unused variable 'ans' [-Wunused-variable]
   90 |         bool ans = 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...