Submission #709487

#TimeUsernameProblemLanguageResultExecution timeMemory
709487uroskJail (JOI22_jail)C++14
49 / 100
5094 ms454540 KiB
#define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include "bits/stdc++.h" //#include <ext/pb_ds/tree_policy.hpp> //#include <ext/pb_ds/assoc_container.hpp> #define ld double #define ll int #define llinf 100000000000000000LL // 10^17 #define pb push_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pll pair<ll,ll> #define pld pair<ld,ld> #define all(a) a.begin(),a.end() #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;} #define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0); using namespace std; //using namespace __gnu_pbds; /* ll add(ll x,ll y){ x+=y; if(x<0){ x%=mod; x+=mod; }else{ if(x>=mod) x%=mod; } return x; } ll mul(ll a,ll b){ ll ans = (a*b)%mod; if(ans<0) ans+=mod; return ans; } typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll rnd(ll l,ll r){ return uniform_int_distribution<ll>(l,r)(rng); } */ #define maxn 3000005 #define lg 22 ll n,m; vector<ll> g[maxn]; vector<ll> v[maxn]; ll tsz = 0; ll id[maxn][lg][2]; ll st[maxn][lg]; ll in[maxn],out[maxn],ti = 0; bool intree(ll x,ll y){return in[y]<=in[x]&&out[x]<=out[y];} ll lca(ll x,ll y){ if(intree(x,y)) return y; if(intree(y,x)) return x; for(ll j = lg-1;j>=0;j--){ if(!intree(x,st[y][j])) y = st[y][j]; } return st[y][0]; } void dfs(ll u,ll p){ in[u] = ++ti; st[u][0] = p; for(ll s : g[u]) if(s!=p) dfs(s,u); out[u] = ti-1; } ll get(ll x,ll y){ for(ll j = lg-1;j>=0;j--){ if(!intree(y,st[x][j])) x = st[x][j]; } return x; } void add(ll x,ll y,bool smer,ll nod){ for(ll j = lg-1;j>=0;j--){ if(!intree(y,st[x][j])){ if(smer) v[id[x][j][1]].pb(nod); else v[nod].pb(id[x][j][0]); x = st[x][j]; } } if(smer) v[id[x][0][1]].pb(nod); else v[nod].pb(id[x][0][0]); if(smer) v[id[y][0][1]].pb(nod); else v[nod].pb(id[y][0][0]); } ll deg[maxn]; void tc(){ ti = 0; cin >> n; for(ll i = 1;i<=n-1;i++){ ll x,y; cin >> x >> y; g[x].pb(y); g[y].pb(x); } dfs(1,1); for(ll i = 1;i<=n;i++) id[i][0][0] = i,id[i][0][1] = i+n; tsz = 2*n; for(ll j = 1;j<lg;j++) for(ll i = 1;i<=n;i++){ st[i][j] = st[st[i][j-1]][j-1]; ++tsz; if(tsz>=maxn){ while(1) here; } id[i][j][0] = tsz; v[tsz].pb(id[i][j-1][0]); v[tsz].pb(id[st[i][j-1]][j-1][0]); ++tsz; if(tsz>=maxn){ while(1) here; } id[i][j][1] = tsz; v[id[i][j-1][1]].pb(tsz); v[id[st[i][j-1]][j-1][1]].pb(tsz); } cin >> m; for(ll i = 1;i<=m;i++){ ll x,y; cin >> x >> y; ++tsz; if(tsz>=maxn){ while(1) here; } v[x].pb(tsz); v[tsz].pb(n+y); ll z = lca(x,y); if(z!=x){ add(x,get(x,z),1,tsz); add(st[x][0],z,0,tsz); } if(z!=y){ add(y,get(y,z),0,tsz); add(st[y][0],z,1,tsz); } } queue<ll> q; for(ll i = 1;i<=tsz;i++) deg[i] = 0; for(ll i = 1;i<=tsz;i++){ for(ll j : v[i]) deg[j]++; } for(ll i = 1;i<=tsz;i++){ if(!deg[i]) q.push(i); } ll cnt = 0; while(q.size()){ ll x = q.front(); q.pop(); cnt++; for(ll y : v[x]){ deg[y]--; if(!deg[y]) q.push(y); } } if(cnt!=tsz) cout<<"No"<<endl; else cout<<"Yes"<<endl; for(ll i = 1;i<=n;i++) g[i].clear(); for(ll i = 1;i<=tsz;i++) v[i].clear(); } int main(){ daj_mi_malo_vremena int t; t = 1; cin >> t; while(t--){ tc(); } return 0; } /** 1 8 1 2 2 3 3 4 4 5 5 6 6 7 7 8 2 3 4 4 8 2 7 1 2 2 3 3 4 4 5 3 6 6 7 2 4 1 5 7 4 1 2 1 3 1 4 3 2 3 3 4 4 2 3 3 1 2 2 3 2 2 1 3 2 7 1 2 2 3 3 4 4 5 5 6 6 7 3 1 3 4 2 2 5 8 1 2 2 3 3 4 4 5 5 6 6 7 7 8 4 1 5 2 6 3 7 4 8 **/
#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...