Submission #874669

#TimeUsernameProblemLanguageResultExecution timeMemory
874669winter0101Jail (JOI22_jail)C++14
100 / 100
803 ms115560 KiB
#include<bits/stdc++.h> using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define pii pair<int,int> #define pli pair<long long,int> #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) #define lastbit(i) __builtin_ctz(i) const int maxn=1e5+2e4+9; vector<int>a[maxn]; pii b[maxn]; int sub[maxn]; int d[maxn],p[maxn]; void dfs(int u,int par){ sub[u]=1; for (auto &v:a[u]){ if (v==par)continue; d[v]=d[u]+1; p[v]=u; dfs(v,u); sub[u]+=sub[v]; if (a[u][0]==par||sub[a[u][0]]<sub[v])swap(a[u][0],v); } } int pos[maxn],h[maxn],tle=0,rev[maxn]; void hld(int u,int par,int head){ pos[u]=++tle; h[u]=head; if (a[u][0]!=par){ hld(a[u][0],u,head); } for (auto v:a[u]){ if (v==par||v==a[u][0])continue; hld(v,u,v); } } vector<int>g[maxn*9];//two segtree and m bool fl=1; int low[maxn*9],num[maxn*9],tme=0; int n,m; void build(int id,int l,int r){ if (l==r){ rev[l]=id; return; } int mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); //-> g[id].pb(id*2); g[id].pb(id*2+1); g[id*2+4*n].pb(id+4*n); g[id*2+1+4*n].pb(id+4*n); } void addedg(int id,int l,int r,int u,int v,int ver){ if (l>v||r<u||u>v)return; //cout<<l<<" "<<r<<" "<<u<<" "<<v<<'\n'; if (u<=l&&r<=v){ g[ver+8*n].pb(id); g[id+4*n].pb(ver+8*n); return; } int mid=(l+r)/2; addedg(id*2,l,mid,u,v,ver); addedg(id*2+1,mid+1,r,u,v,ver); } void takepath(int id,int u,int v){ bool f1=1,f2=1; while (h[u]!=h[v]){ if (d[h[u]]<d[h[v]]){ swap(f1,f2); swap(u,v); } addedg(1,1,n,pos[h[u]],pos[u]-f1,id); f1=0; u=p[h[u]]; } if (pos[u]>pos[v]){ swap(u,v); swap(f1,f2); } addedg(1,1,n,pos[u]+f1,pos[v]-f2,id); } stack<int>t; void redfs(int u){ t.push(u); low[u]=num[u]=++tme; for (auto v:g[u]){ if (num[v]==-1)continue; if (num[v])low[u]=min(low[u],low[v]); else { redfs(v); low[u]=min(low[u],low[v]); } } if (low[u]==num[u]){ int dem=0; while (!t.empty()&&t.top()!=u){ num[t.top()]=-1; dem+=(t.top()>8*n); t.pop(); } dem+=(u>8*n); if (dem>1)fl=0; num[u]=-1; t.pop(); } } int t1[maxn]; void solve(){ cin>>n; for1(i,1,n){ a[i].clear(); t1[i]=0; } for1(i,1,9*n){ g[i].clear(); num[i]=low[i]=0; } for1(i,1,n-1){ int u,v; cin>>u>>v; a[u].pb(v); a[v].pb(u); } dfs(1,0); tle=0; hld(1,0,1); build(1,1,n); cin>>m; for1(i,1,m){ cin>>b[i].fi>>b[i].se; g[i+8*n].pb(rev[pos[b[i].fi]]+4*n); g[rev[pos[b[i].se]]].pb(i+8*n); t1[b[i].se]=i; takepath(i,b[i].fi,b[i].se); } for1(i,1,m){ if (t1[b[i].fi]){ g[i+8*n].pb(t1[b[i].fi]+8*n); //cout<<i<<" "<<t1[b[i].fi]<<'\n'; } } //takepath(2,b[2].fi,b[2].se); tme=0; fl=1; for1(i,1,8*n+m)if (!num[i])redfs(i); if (fl)cout<<"Yes"<<'\n'; else cout<<"No"<<'\n'; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen("temp.INP","r",stdin); //freopen("temp.OUT","w",stdout); int test=1; cin>>test; while (test--)solve(); }
#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...