oj.uz

Submission #548050

# Submission time Handle Problem Language Result Execution time Memory
548050 2022-04-12T09:46:56 Z fcmalkcin Jail (JOI22_jail) C++17
5 / 100
 5000 ms 834960 KB 
#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)
        {
            /*  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: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: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 15 ms 29396 KB Output is correct
2 Correct 16 ms 29516 KB Output is correct
3 Correct 17 ms 29428 KB Output is correct
4 Correct 31 ms 29556 KB Output is correct
5 Correct 47 ms 29524 KB Output is correct
6 Correct 20 ms 29524 KB Output is correct
7 Correct 18 ms 29524 KB Output is correct
8 Correct 19 ms 29504 KB Output is correct
9 Correct 72 ms 31824 KB Output is correct
10 Correct 77 ms 55840 KB Output is correct
11 Correct 26 ms 29524 KB Output is correct
12 Correct 76 ms 30060 KB Output is correct
13 Correct 233 ms 67996 KB Output is correct
14 Correct 125 ms 62668 KB Output is correct
15 Correct 213 ms 63292 KB Output is correct
16 Correct 369 ms 70036 KB Output is correct
17 Correct 273 ms 71080 KB Output is correct
18 Correct 326 ms 66720 KB Output is correct
19 Correct 260 ms 70512 KB Output is correct
20 Correct 183 ms 65792 KB Output is correct
21 Correct 235 ms 69692 KB Output is correct
22 Correct 120 ms 60280 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29464 KB Output is correct
2 Correct 17 ms 29460 KB Output is correct
3 Correct 17 ms 29612 KB Output is correct
4 Execution timed out 5099 ms 834960 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29464 KB Output is correct
2 Correct 17 ms 29460 KB Output is correct
3 Correct 17 ms 29612 KB Output is correct
4 Execution timed out 5099 ms 834960 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29464 KB Output is correct
2 Correct 17 ms 29460 KB Output is correct
3 Correct 17 ms 29612 KB Output is correct
4 Execution timed out 5099 ms 834960 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29464 KB Output is correct
2 Correct 17 ms 29460 KB Output is correct
3 Correct 17 ms 29612 KB Output is correct
4 Execution timed out 5099 ms 834960 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 29512 KB Output is correct
2 Correct 16 ms 29396 KB Output is correct
3 Correct 15 ms 29460 KB Output is correct
4 Correct 19 ms 29440 KB Output is correct
5 Correct 34 ms 29516 KB Output is correct
6 Correct 18 ms 29496 KB Output is correct
7 Correct 17 ms 29524 KB Output is correct
8 Execution timed out 5077 ms 29396 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29396 KB Output is correct
2 Correct 16 ms 29516 KB Output is correct
3 Correct 17 ms 29428 KB Output is correct
4 Correct 31 ms 29556 KB Output is correct
5 Correct 47 ms 29524 KB Output is correct
6 Correct 20 ms 29524 KB Output is correct
7 Correct 18 ms 29524 KB Output is correct
8 Correct 19 ms 29504 KB Output is correct
9 Correct 72 ms 31824 KB Output is correct
10 Correct 77 ms 55840 KB Output is correct
11 Correct 26 ms 29524 KB Output is correct
12 Correct 76 ms 30060 KB Output is correct
13 Correct 233 ms 67996 KB Output is correct
14 Correct 125 ms 62668 KB Output is correct
15 Correct 213 ms 63292 KB Output is correct
16 Correct 369 ms 70036 KB Output is correct
17 Correct 273 ms 71080 KB Output is correct
18 Correct 326 ms 66720 KB Output is correct
19 Correct 260 ms 70512 KB Output is correct
20 Correct 183 ms 65792 KB Output is correct
21 Correct 235 ms 69692 KB Output is correct
22 Correct 120 ms 60280 KB Output is correct
23 Correct 18 ms 29464 KB Output is correct
24 Correct 17 ms 29460 KB Output is correct
25 Correct 17 ms 29612 KB Output is correct
26 Execution timed out 5099 ms 834960 KB Time limit exceeded
27 Halted 0 ms 0 KB -