oj.uz

Submission #548049

# Submission time Handle Problem Language Result Execution time Memory
548049 2022-04-12T09:46:09 Z fcmalkcin Jail (JOI22_jail) C++17
5 / 100
 5000 ms 1048576 KB 
#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=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)
        {
            /*  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(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;
        }
        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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33224 KB Output is correct
2 Correct 18 ms 33236 KB Output is correct
3 Correct 17 ms 33236 KB Output is correct
4 Correct 30 ms 33344 KB Output is correct
5 Correct 46 ms 33328 KB Output is correct
6 Correct 18 ms 33264 KB Output is correct
7 Correct 17 ms 33364 KB Output is correct
8 Correct 19 ms 33364 KB Output is correct
9 Correct 62 ms 36400 KB Output is correct
10 Correct 82 ms 72856 KB Output is correct
11 Correct 25 ms 33184 KB Output is correct
12 Correct 74 ms 33852 KB Output is correct
13 Correct 271 ms 86568 KB Output is correct
14 Correct 145 ms 80980 KB Output is correct
15 Correct 229 ms 83412 KB Output is correct
16 Correct 450 ms 95496 KB Output is correct
17 Correct 313 ms 95148 KB Output is correct
18 Correct 323 ms 83936 KB Output is correct
19 Correct 283 ms 93896 KB Output is correct
20 Correct 196 ms 87096 KB Output is correct
21 Correct 279 ms 93280 KB Output is correct
22 Correct 124 ms 77564 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33284 KB Output is correct
2 Correct 17 ms 33264 KB Output is correct
3 Correct 19 ms 33376 KB Output is correct
4 Runtime error 3609 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33284 KB Output is correct
2 Correct 17 ms 33264 KB Output is correct
3 Correct 19 ms 33376 KB Output is correct
4 Runtime error 3609 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33284 KB Output is correct
2 Correct 17 ms 33264 KB Output is correct
3 Correct 19 ms 33376 KB Output is correct
4 Runtime error 3609 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33284 KB Output is correct
2 Correct 17 ms 33264 KB Output is correct
3 Correct 19 ms 33376 KB Output is correct
4 Runtime error 3609 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33236 KB Output is correct
2 Correct 18 ms 33236 KB Output is correct
3 Correct 18 ms 33236 KB Output is correct
4 Correct 20 ms 33224 KB Output is correct
5 Correct 41 ms 33424 KB Output is correct
6 Correct 21 ms 33380 KB Output is correct
7 Correct 20 ms 33368 KB Output is correct
8 Execution timed out 5089 ms 33236 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33224 KB Output is correct
2 Correct 18 ms 33236 KB Output is correct
3 Correct 17 ms 33236 KB Output is correct
4 Correct 30 ms 33344 KB Output is correct
5 Correct 46 ms 33328 KB Output is correct
6 Correct 18 ms 33264 KB Output is correct
7 Correct 17 ms 33364 KB Output is correct
8 Correct 19 ms 33364 KB Output is correct
9 Correct 62 ms 36400 KB Output is correct
10 Correct 82 ms 72856 KB Output is correct
11 Correct 25 ms 33184 KB Output is correct
12 Correct 74 ms 33852 KB Output is correct
13 Correct 271 ms 86568 KB Output is correct
14 Correct 145 ms 80980 KB Output is correct
15 Correct 229 ms 83412 KB Output is correct
16 Correct 450 ms 95496 KB Output is correct
17 Correct 313 ms 95148 KB Output is correct
18 Correct 323 ms 83936 KB Output is correct
19 Correct 283 ms 93896 KB Output is correct
20 Correct 196 ms 87096 KB Output is correct
21 Correct 279 ms 93280 KB Output is correct
22 Correct 124 ms 77564 KB Output is correct
23 Correct 17 ms 33284 KB Output is correct
24 Correct 17 ms 33264 KB Output is correct
25 Correct 19 ms 33376 KB Output is correct
26 Runtime error 3609 ms 1048576 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -