제출 #885282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
885282		Ahmed57	Jail (JOI22_jail)	C++17	49 / 100	411 ms	312424 KiB

jail

#include <bits/stdc++.h>
 
using namespace std;
int P[120001][17];
int lola[120001][17];
int lolb[120001][17];
int lolc[120001],dep[120001];
vector<int> adj[120001],tree[120005+120000*17];
    int deg[120005+120000*17] = {0};
void dfs(int i,int pr){
    P[i][0] = pr;
    dep[i] = dep[pr]+1;
    for(int j = 1;j<17;j++){
        P[i][j] = P[P[i][j-1]][j-1];
    }
    for(auto j:adj[i]){
        if(j==pr)continue;
        dfs(j,i);
    }
}
int go(int x,int len){
    for(int i = 16;i>=0;i--){
        if(len>=(1<<i)){
            x = P[x][i];
            len-=(1<<i);
        }
    }
    return x;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;cin>>t;while(t--){
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++){
        adj[i].clear();
    }
    for(int i = 1;i<n;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int q;cin>>q;
    vector<pair<int,int>> v;v.push_back({0,0});
    for(int i = 1;i<=q;i++){
        int a,b;cin>>a>>b;
        v.push_back({a,b});
    }
    dfs(1,0);
    int NODES = 0;
    for(int i = 1;i<=q;i++){
        lolc[i] = ++NODES;
        //cout<<lolc[i]<<endl;
    }
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<=log2(n);j++){
            lola[i][j] = ++NODES;
            lolb[i][j] = ++NODES;
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=log2(n);j++){
            tree[lolb[i][j]].push_back(lolb[i][j-1]);
            tree[lolb[i][j]].push_back(lolb[P[i][j-1]][j-1]);
            tree[lola[i][j-1]].push_back(lola[i][j]);
            tree[lola[P[i][j-1]][j-1]].push_back(lola[i][j]);            
        }
    }
    //cout<<tree[0].size()<<endl;
    for(int i = 1;i<=q;i++){
        tree[lolc[i]].push_back(lola[v[i].first][0]);
        tree[lolb[v[i].second][0]].push_back(lolc[i]);
    }
    for(int i = 1;i<=q;i++){
        int x,y;
        x = v[i].first , y = v[i].second;
        if(dep[x]>dep[y]&&go(x,dep[x]-dep[y])==y){
            y=go(x,dep[x]-dep[y]-1);
        }else y = P[y][0];
        //cout<<x<<" "<<y<<endl;
        if(dep[x]<dep[y])swap(x,y);
        for(int j =log2(n);j>=0;j--){
            if(dep[x]-(1<<j)>=dep[y]){
                tree[lolc[i]].push_back(lolb[x][j]);
                x = P[x][j];
            }
        }
        for(int j = log2(n);j>=0;j--){
            if(P[x][j]!=P[y][j]){
                tree[lolc[i]].push_back(lolb[x][j]);
                tree[lolc[i]].push_back(lolb[y][j]);
                x = P[x][j];y = P[y][j];
            }
        }
        tree[lolc[i]].push_back(lolb[x][0]);
        if(x!=y)tree[lolc[i]].push_back(lolb[y][1]);
        x = v[i].first , y = v[i].second;
        if(dep[y]>dep[x]&&go(y,dep[y]-dep[x])==x){
            x=go(y,dep[y]-dep[x]-1);
        }else x = P[x][0];
        if(dep[x]<dep[y])swap(x,y);
        for(int j = log2(n);j>=0;j--){
            if(dep[x]-(1<<j)>=dep[y]){
                tree[lola[x][j]].push_back(lolc[i]);
                x = P[x][j];
            }
        }
        for(int j =log2(n);j>=0;j--){
            if(P[x][j]!=P[y][j]){
                tree[lola[x][j]].push_back(lolc[i]);
                tree[lola[y][j]].push_back(lolc[i]);
                x = P[x][j];y = P[y][j];
            }
        }
        tree[lola[x][0]].push_back(lolc[i]);
        if(x!=y){tree[lola[y][1]].push_back(lolc[i]);}
    }
    //cout<<"ggg"<<endl;
    tree[0].clear();
    for(int i = 0;i<=NODES;i++){
        for(auto j:tree[i]){
            //if(j>NODES||j==0)assert(0);
            deg[j]++;
        }
    }
    queue<int> qe;
    for(int i = 0;i<=NODES;i++){
        if(deg[i]==0){
            qe.push(i);
        }
    }
    int cnt = 0;
    while(!qe.empty()){
        int x = qe.front();qe.pop();
        cnt++;
        for(auto j:tree[x]){
            deg[j]--;
            if(deg[j]==0)qe.push(j);
        }
    }
    for(int i = 0;i<=NODES;i++){
        //cout<<vis[i]<<" "<<i<<endl;
    }
    if(cnt==NODES+1)cout<<"Yes\n";
    else cout<<"No\n";
    for(int i = 0;i<=NODES;i++){tree[i].clear();deg[i] = 0;}
}
}

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