Submission #545005

#TimeUsernameProblemLanguageResultExecution timeMemory
545005leakedJail (JOI22_jail)C++14
49 / 100
509 ms327480 KiB
#include <bits/stdc++.h> #define f first #define s second #define m_p make_pair #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define vec vector #define pb push_back #define sz(x) (int)(x).size() #define pw(x) (1LL<<(x)) #define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef long double ld; typedef pair<int,ll> pil; template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);} template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);} const int M=1e9+7; const int N=120'000+1; const int lg=19; void add(int &a,int b){ a+=b; if(a>=M) a-=M; else if(a<0) a+=M; } int mult(int a,int b){ return 1ll*a*b%M; } vec<int> gr[N*lg],g[N]; int used[N],ok; int up[N][lg]; int fin[N][lg],sta[N][lg]; void dfs(int v){ used[v]=1; for(auto &z : gr[v]){ if(used[z]){ ok&=(used[z]==2); continue; } dfs(z); } used[v]=2; } int par[N],in[N],out[N],tt,ut[N],dt[N]; int id=0; void dfs1(int v,int p){ par[v]=p; in[v]=tt++; ut[v]=(ut[v]==-1?id++:ut[v]); dt[v]=(dt[v]==-1?id++:dt[v]); up[v][0]=p; sta[v][0]=id++;fin[v][0]=id++; // cout<<"ADD "<<fin[v][0]<<' '<<dt[p]<<endl; gr[fin[v][0]].pb(dt[p]); gr[ut[p]].pb(sta[v][0]); // cout<<"ADD "<<ut[p]<<' ' <<sta[v][0]<<endl; // cout<<"DFS "<<v<<endl; for(int j=1;j<lg;j++){ up[v][j]=up[up[v][j-1]][j-1]; sta[v][j]=id++;fin[v][j]=id++; // cout<<"ADDT1 "<<fin[v][j]<<' '<<fin[v][j-1]<<' '<<fin[up[v][j-1]][j-1]<<endl; gr[fin[v][j]].pb(fin[v][j-1]);gr[fin[v][j]].pb(fin[up[v][j-1]][j-1]); // cout<<"ADDT2 "<<sta[v][j-1]<<' '<<sta[up[v][j-1]][j-1]<<' '<<sta[v][j]<<endl; gr[sta[v][j-1]].pb(sta[v][j]);gr[sta[up[v][j-1]][j-1]].pb(sta[v][j]); } for(auto &z : g[v]){ if(z==p) continue; dfs1(z,v); } out[v]=tt-1; } bool is(int a,int b){ return in[a]<=in[b]&&out[a]>=out[b]; } int lca(int a,int b){ if(is(a,b)) return a; for(int i=lg-1;i>=0;i--){ if(!is(up[a][i],b)) a=up[a][i]; } return up[a][0]; } void addway(int a,int b,int j){ if(is(a,b)) return; for(int i=lg-1;i>=0;i--){ if(!is(up[a][i],b)){ // cout<<"ADD "<<sta[a][i]<<' '<<j<<endl; // cout<<"ADD "<<j<<' '<<fin[a][i]<<endl; gr[sta[a][i]].pb(j); gr[j].pb(fin[a][i]); a=up[a][i]; } } // int i=0; // gr[j].pb(gu[a][i]); // gr[gd[a][i]].pb(j); } void solve(){ int n,m; cin>>n; for(int i=0;i<n;i++) ut[i]=dt[i]=-1,g[i].clear(); ok=1; for(int i=1;i<n;i++){ int v,u; cin>>v>>u;--v;--u; g[v].pb(u);g[u].pb(v); } cin>>m; vec<int> st(m),f(m); for(int i=0;i<m;i++) used[i]=0,gr[i].clear(); // vec<int>ids(m); id=m; for(int i=0;i<m;i++){ cin>>st[i]>>f[i];--st[i];--f[i]; ut[st[i]]=i;dt[f[i]]=i; } dfs1(0,0); ///ut - start , dt - finish for(int i=0;i<m;i++){ // gr[ut[f[i]]].pb(ids[i]); // gr[ids[i]].pb(dt[st[i]]); int v=st[i],u=f[i]; int lc=lca(v,u); addway(v,lc,i);addway(u,lc,i); gr[i].pb(dt[st[i]]); gr[ut[f[i]]].pb(i); // if(lc!=v && lc!=u){ gr[i].pb(dt[lc]); gr[ut[lc]].pb(i); } } for(int i=0;i<id;i++){ if(!used[i]) dfs(i); } for(int i=0;i<id;i++) gr[i].clear(),used[i]=0; id=0; cout<<(ok?"Yes":"No")<<'\n'; } signed main(){ fast_resp; int t; cin>>t; while(t--){ solve(); } return 0; } /* 1 4 1 2 2 3 3 4 4 5 3 6 6 7 1 4 1 5 7 */
#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...