Submission #1259170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259170		user736482	Jail (JOI22_jail)	C++20	0 / 100	46 ms	73796 KiB

jail

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define INF 1000000019
#define POT (1<<21)
#define INFL 1000000000000000099LL
#define LG 3
int par[120000+1][LG],idxg[120001][LG][2],dpt[120000],dg[120000];
vector<ll>g[120000+1],g2[3000000];
ll a,b,n,m;
void dfs(ll v,ll pop,ll dp){
    par[v][0]=pop;
    dpt[v]=dp;
    for(ll i : g[v]){
        if(i!=pop)dfs(i,v,dp+1);
    }
}
ll ak;
void solve(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        g[i].clear();
    }
    for(ll i=1;i<n;i++){
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
    }
    dfs(1,1,0);
    ak=2*n+1;// i<=n oznacza v poczatkow <=n, i<=2*n to v koncow
    cin>>m;
    vector<pair<ll,ll>>pth;
    vector<ll>idx;
    for(ll i=0;i<m;i++){
        cin>>a>>b;
        pth.pb({a,b});
        idx.pb(ak++);
        g2[ak-1].pb(a);
        g2[n+b].pb(ak-1);
    }
    for(ll i=1;i<=n;i++){
        if(i==1){
            idxg[i][0][0]=0;
            idxg[i][0][1]=ak++;
            continue;
        }
        idxg[i][0][0]=par[i][0];
        idxg[i][0][1]=n+par[i][0];
        //idxg[i][0][0]=ak;//0 - przed
        //g2[i].pb(ak);
        //g2[par[i][0]].pb(ak++);
        //idxg[i][0][1]=ak;//1 - po
        //g2[ak].pb(i+n);
        //g2[ak++].pb(par[i][0]+n);
    }
    for(ll i=0;i<ak;i++){
    }
    for(ll i=1;i<=n;i++){
   //    cout<<i<<" "<<0<<" "<<idxg[i][0][0]<<" "<<idxg[i][0][1]<<"\n";
    }
    for(ll j=1;j<LG;j++){
        for(ll i=1;i<=n;i++){
            par[i][j]=par[par[i][j-1]][j-1];
            idxg[i][j][0]=ak;//0 - przed
            g2[idxg[i][j-1][0]].pb(ak);
            g2[idxg[par[i][j-1]][j-1][0]].pb(ak++);
            idxg[i][j][1]=ak;//1 - po
            g2[ak].pb(idxg[i][j-1][1]);
            g2[ak++].pb(idxg[par[i][j-1]][j-1][1]);
         //   cout<<i<<" "<<j<<" "<<idxg[i][j][0]<<" "<<idxg[i][j][1]<<"\n";
        }
    }
    for(ll i=0;i<ak;i++){
      //  cout<<i<<": ";
      //  for(ll j : g2[i])cout<<j<<" ";
      //  cout<<"\n";
    }
   // cout<<"\n\n";
    for(ll i=0;i<m;i++){
        
        a=pth[i].ff;
        b=pth[i].ss;
        ll moj=idx[i];
        g2[moj].pb(a+n);
        g2[b].pb(moj);
       // cout<<moj<<" "<<a<<" "<<b<<"     ";
        if(dpt[a]<dpt[b])swap(a,b);
        ll k=dpt[a]-dpt[b];
        
        for(ll j=LG-1;j>=0;j--){
            if((k & (1<<j))){
                if(par[a][j]==b){
                    k--;
                    continue;
                }
                //cout<<a<<" "<<j<<" ";
                g2[idxg[a][j][0]].pb(moj);
                g2[moj].pb(idxg[a][j][1]);
                a=par[a][j];
            }
        }
        if(b==par[a][0])continue;
        for(ll j=LG-1;j>=0;j--){
            if(par[a][j]!=par[b][j]){
                g2[idxg[a][j][0]].pb(moj);
                g2[moj].pb(idxg[a][j][1]);
                a=par[a][j];
                g2[idxg[b][j][0]].pb(moj);
                g2[moj].pb(idxg[b][j][1]);
                b=par[b][j];
            }
        }
        ll j=0;
        g2[idxg[a][j][0]].pb(moj);
        g2[moj].pb(idxg[a][j][1]);
        a=par[a][j];
        g2[idxg[b][j][0]].pb(moj);
        g2[moj].pb(idxg[b][j][1]);
        b=par[b][j];
    }
    for(ll i=0;i<ak;i++){
      //  cout<<i<<": ";
      //  for(ll j : g2[i])cout<<j<<" ";
      //  cout<<"\n";
    }
    for(ll i=0;i<ak;i++){
        for(ll j : g2[i])dg[j]++;
    }
    queue<int>q;
    ll x=0;
    for(ll i=0;i<ak;i++){
        if(dg[i]==0)q.push(i);
    }
    //cout<<dg[5]<<" ";
    while(q.size()){
        a=q.front();
        //cout<<a<<" ";
        q.pop();
        x++;
        for(ll i : g2[a]){
            dg[i]--;
            if(dg[i]==0)q.push(i);
        }
    }
  //  cout<<x<<" "<<ak<<" ";
    if(x==ak)cout<<"Yes\n";
    else cout<<"No\n";
    for(ll i=0;i<ak;i++){g2[i].clear();dg[i]=0;}
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll T;
    cin>>T;
    while(T--){solve();}
}

• 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