Submission #548053

#TimeUsernameProblemLanguageResultExecution timeMemory
548053fcmalkcinJail (JOI22_jail)C++17
54 / 100
392 ms71572 KiB
#include<bits/stdc++.h> using namespace std; #define ll int #define pll pair<ll,ll> #define ff first #define ss second #define endl "\n" #define pb push_back #define F(i,a,b) for(ll i=a;i<=b;i++) const ll maxn=1e5+2e4+100; const ll base=3e18; const ll mod= 1e9+7 ; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); /// have medal in APIO /// goal 2/8 struct tk { ll pos; ll pos1; tk () { pos=-1; pos1=-1; } }; ll id1[maxn]; tk st[4*maxn]; vector<ll> st1[4*maxn][2]; ll col[maxn]; tk mer(tk a,tk b) { a.pos=max(a.pos,b.pos); a.pos1=max(a.pos1,b.pos1); return a; } bool chk1(ll u,ll c) { if (u==-1) return true; return (col[u]==c); } tk getr(ll id,ll l,ll r,ll x) { tk c; if (x>r||x<l) return c; for (int t=0; t<=1; t++) { bool chk=false; while (st1[id][t].size()) { ll h=st1[id][t].back(); st1[id][t].pop_back(); if (!chk1(h,t)) continue; if (h==id1[x]) { chk=true; continue; } if (t==0) c.pos=h; else c.pos1=h; break; } if (chk) st1[id][t].pb(id1[x]); } // cout <<l<<" "<<r<<" chk2"<<endl; if (l==r) return c; ll mid=(l+r)/2; return mer(c,mer(getr(id*2,l,mid,x),getr(id*2+1,mid+1,r,x))); } void updater(ll id,ll l,ll r,ll x,ll y,ll p,ll t) { if (x>r||y<l) return ; if (x<=l&&y>=r) { st1[id][t].pb(p); return ; } ll mid=(l+r)/2; updater(id*2,l,mid,x,y,p,t); updater(id*2+1,mid+1,r,x,y,p,t); } tk get(ll id,ll l,ll r,ll x,ll y) { tk c; if (x>r||y<l) return c; if (x<=l&&y>=r) return st[id]; ll mid=(l+r)/2; return mer(get(id*2,l,mid,x,y),get(id*2+1,mid+1,r,x,y)); } void update(ll id,ll l,ll r,ll x,ll diff) { if (x>r||x<l) return ; if (l==r) { tk c; st[id]=c; if (diff==0) st[id].pos=id1[l]; else if (diff==1) st[id].pos1=id1[l]; return ; } ll mid=(l+r)/2; update(id*2,l,mid,x,diff); update(id*2+1,mid+1,r,x,diff); st[id]=mer(st[id*2],st[id*2+1]); } ll pos[maxn]; ll c=1; ll cnt=0; ll nc[maxn]; ll nch[maxn]; ll anc[maxn][20]; ll dep[maxn]; vector<ll> adj[maxn]; ll siz[maxn]; ll nxt[maxn]; ll pre[maxn]; ll n; ll lca(ll x,ll y) { if (dep[x]<dep[y]) swap(x,y); ll kc=dep[x]-dep[y]; for (int i=19; i>=0; i--) if (kc&(1ll<<i)) x=anc[x][i]; if (x==y) return x; for (int i=19; i>=0; i--) if (anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i]; return anc[x][0]; } void dfs(ll u,ll par) { siz[u]=1; anc[u][0]=par; for (int i=1; i<=19; i++) anc[u][i]=anc[anc[u][i-1]][i-1]; for (auto to:adj[u]) { if (to==par) continue; dep[to]=dep[u]+1; dfs(to,u); siz[u]+=siz[to]; } } void hld(ll u,ll par) { cnt++; id1[cnt]=u; pos[u]=cnt; nc[u]=c; if (!nch[nc[u]]) nch[nc[u]]=u; pll mx=make_pair(0,0); for (auto to:adj[u]) { if (to==par) continue; mx=max(mx,make_pair(siz[to],to)); } if (mx.ss) hld(mx.ss,u); for (auto to:adj[u]) { if (to==par||to==mx.ss) continue; c++; hld(to,u); } } bool chkall; ll getnear(ll u,ll x) { if (dep[u]<dep[x]) swap(u,x); ll kc=dep[u]-dep[x]-1; for (int i=19; i>=0; i--) if (kc&(1ll<<i)) u=anc[u][i]; return u; } tk get1(ll x,ll u) { tk a; while (1) { if (nc[x]==nc[u]) { a=mer(a,get(1,1,n,pos[u],pos[x])); break; } else { ll h=nch[nc[x]]; a=mer(a,get(1,1,n,pos[h],pos[x])); x=anc[h][0]; } } return a; } void update1(ll x,ll u,ll p,ll t) { while (1) { if (nc[x]==nc[u]) { updater(1,1,n,pos[u],pos[x],p,t); break; } else { ll h=nch[nc[x]]; updater(1,1,n,pos[h],pos[x],p,t); x=anc[h][0]; } } } void dfs1(ll u) { if (!chkall) return ; // cout <<u<<" chk1"<<endl; col[u]=1; ll h=nxt[u]; update(1,1,n,pos[h],1); ll l=lca(u,h); update1(u,l,u,1); update1(h,l,u,1); vector<pll> vt; if (h==l) { vt.pb(make_pair(u,getnear(u,l))); } else { vt.pb(make_pair(u,l)); vt.pb(make_pair(anc[h][0],l)); } while (1) { tk nw; for (auto p:vt) nw=mer(nw,get1(p.ff,p.ss)); if (nw.pos1!=-1) { /* cout <<u<<" wtf"<<endl; cout <<nw.pos1<<" "<<nw.pos<<" wtf"<<endl; for (auto to:vt) { cout <<to.ff<<" "<<to.ss<<endl; }*/ chkall=false; return ; } else if (nw.pos!=-1) { /*if (u==2) { cout <<"WTF"<<" "<<nw.pos<<" "<<pre[nw.pos]<<endl; }*/ dfs1(pre[nw.pos]); } else break; } while (1) { tk nw=getr(1,1,n,pos[u]); /*if (u==3) { cout <<nw.pos<<" "<<nw.pos1<<endl; }*/ if (nw.pos1!=-1) { chkall=false; return ; } else if (nw.pos!=-1) { dfs1(nw.pos); } else break; } col[u]=2; update(1,1,n,pos[h],2); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("t.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } ll t; cin>> t; while (t--) { chkall=true; cin>> n; for (int i=1; i<=n-1; i++) { ll x, y; cin>>x>> y; adj[x].pb(y); adj[y].pb(x); } dfs(1,0); c=1; cnt=0; hld(1,0); ll m; cin>> m; for (int i=1; i<=m; i++) { ll x, y; cin>>x>> y; nxt[x]=y; pre[y]=x; } for (int i=1; i<=n; i++) { if (pre[i]) { ll h=pos[i]; //cout <<i<<" "<<h<<" chk1"<<endl; update(1,1,n,h,0); ll u=pre[i]; h=i; ll l=lca(u,h); // cout <<u<<" "<<h<<" "<<l<<endl; update1(u,l,u,0); update1(h,l,u,0); } } for (int i=1; i<=n; i++) { if (nxt[i]&&!col[i]) { // cout <<i<<" "<<col[i]<<" chkdfs"<<endl; dfs1(i); } } if (chkall) cout <<"Yes"<<endl; else cout <<"No"<<endl; for (int i=1; i<=n; i++) { adj[i].clear(); nxt[i]=0; pre[i]=0; col[i]=0; nch[i]=0; } for (int i=1; i<=4*n; i++) { tk c; st[i]=c; st1[i][0].clear(); st1[i][1].clear(); } } } /* 1 5 1 2 1 3 3 4 4 5 2 2 4 3 2 */

Compilation message (stderr)

jail.cpp:13:15: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+18' to '2147483647' [-Woverflow]
   13 | const ll base=3e18;
      |               ^~~~
jail.cpp: In function 'int main()':
jail.cpp:313:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  313 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jail.cpp:314:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  314 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...