Submission #548059

#	Time	Username	Problem	Language	Result	Execution time	Memory
548059		fcmalkcin	Jail (JOI22_jail)	C++17	100 / 100	864 ms	75584 KiB

jail

#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 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]);
    }
    if (c.pos!=-1) st1[id][0].pb(c.pos);
    if (c.pos1!=-1) st1[id][1].pb(c.pos1);
  //  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
9
1 2
1 3
3 4
2 5
1 6
5 7
3 8
8 9
4
9 2
6 1
4 5
3 4

*/

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23