Submission #547999

#	Time	Username	Problem	Language	Result	Execution time	Memory
547999		fcmalkcin	Jail (JOI22_jail)	C++17	0 / 100	34 ms	43536 KiB

jail

#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=5e5+100;
const ll base=300;
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];
tk mer(tk a,tk b)
{
    a.pos=max(a.pos,b.pos);
    a.pos1=max(a.pos1,b.pos1);
    return a;
}
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 col[maxn];
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 dfs1(ll u)
{
    col[u]=1;
    ll h=nxt[u];
    update(1,1,n,pos[h],1);
    ll l=lca(u,h);
    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)
        {
            dfs1(pre[nw.pos]);
        }
        else
            break;
    }

    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);
            }
        }
        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;
        }
        for (int i=1; i<=4*n; i++)
        {
            tk c;
            st[i]=c;
        }
    }
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:215:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jail.cpp:216:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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