Submission #544563

#	Time	Username	Problem	Language	Result	Execution time	Memory
544563		Rafi22	Jail (JOI22_jail)	C++14	100 / 100	2849 ms	292860 KiB

jail

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=120007;

vector<int>G[N];
int skok[N][17];
vector<int>G1[N*37];
int ile[N*37];
int pre[N],post[N],c;
int n;

void edge(int u,int v)
{
    //cout<<u<<" "<<v<<endl;
    G1[u].pb(v);
    ile[v]++;
}

void dfs(int v,int o)
{
    pre[v]=++c;
    skok[v][0]=o;
    edge(n+v,v);
    edge(n+v,o);
    edge(v+n*18,n+v+n*18);
    edge(o+n*18,n+v+n*18);
    for(int i=1;i<17;i++)
    {
        skok[v][i]=skok[skok[v][i-1]][i-1];
        edge((i+1)*n+v,i*n+v);
        edge((i+1)*n+v,i*n+skok[v][i-1]);
        edge(i*n+v+n*18,(i+1)*n+v+n*18);
        edge(i*n+skok[v][i-1]+n*18,(i+1)*n+v+n*18);
    }
    for(auto u:G[v])
    {
        if(u==o) continue;
        dfs(u,v);
    }
    post[v]=c;
}

bool anc(int u,int v){return pre[u]<=pre[v]&&post[u]>=post[v];}
int lca(int u,int v)
{
    if(anc(u,v)) return u;
    for(int i=16;i>=0;i--) if(!anc(skok[u][i],v)) u=skok[u][i];
    return skok[u][0];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt,xd=0;
    cin>>tt;
    while(tt--)
    {
        int a,b,m;
        cin>>n;
        for(int i=1;i<n;i++)
        {
            cin>>a>>b;
            G[a].pb(b);
            G[b].pb(a);
        }
        c=0;
        dfs(1,1);
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>a>>b;
            edge(a,b);
            edge(a+n*18,a);
            int l=lca(a,b);
           // cout<<l<<endl;
            if(a!=l)
            {
                edge(a,l);
                int x=skok[a][0];
                if(x!=l&&skok[x][0]==l)
                {
                    edge(a,x);
                    edge(x+n*18,a);
                }
                for(int j=16;j>=0;j--)
                {
                    if(!anc(skok[x][j],l))
                    {
                        //cout<<"XD"<<skok[x][j]<<endl;
                        edge(a,(j+1)*n+x);
                        edge((j+1)*n+x+n*18,a);
                        x=skok[x][j];
                    }
                }
            }
            if(b!=l)
            {
                edge(l+n*18,a);
                int x=skok[b][0];
                if(x!=l&&skok[x][0]==l)
                {
                    edge(a,x);
                    edge(x+n*18,a);
                }
                for(int j=16;j>=0;j--)
                {
                    if(!anc(skok[x][j],l))
                    {
                        edge(a,(j+1)*n+x);
                        edge((j+1)*n+x+n*18,a);
                        x=skok[x][j];
                    }
                }
            }
            edge(a,b+n*18);
        }
        deque<int>Q;
        for(int i=1;i<=n*36;i++) if(ile[i]==0) Q.pb(i);
        int c=0;
        while(sz(Q)>0)
        {
            int v=Q[0];
            Q.pop_front();
            c++;
            for(auto u:G1[v])
            {
                ile[u]--;
                if(ile[u]==0) Q.pb(u);
            }
        }
        if(c==n*36) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        for(int i=1;i<=n;i++) G[i].clear();
        for(int i=1;i<=n*36;i++)
        {
            ile[i]=0;
            G1[i].clear();
        }
    }

    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:69:12: warning: unused variable 'xd' [-Wunused-variable]
   69 |     int tt,xd=0;
      |            ^~

• 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