| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 548054 | fcmalkcin | Jail (JOI22_jail) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#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=2e5+100
//const ll maxn=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("test.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
*/