제출 #713576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713576		mraron	Jail (JOI22_jail)	C++14	100 / 100	1755 ms	310416 KiB

jail

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair
#define ins insert

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

using ll = long long;
using ull = unsigned long long ;
using ld = long double ;
using str = string;
using ordered_set=tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>;

const double PI=acos(-1);
const ll INF = 1LL<<62;
const ll MINF = -(1LL<<62);

template<typename T> T getint() {
    T val=0;
    char c;
    
    bool neg=false;
    while((c=gc()) && !(c>='0' && c<='9')) {
        neg|=c=='-';
    }

    do {
        val=(val*10)+c-'0';
    } while((c=gc()) && (c>='0' && c<='9'));

    return val*(neg?-1:1);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)

template<int L=20>
struct lca {
    int n, lg;
    vector<int> par, lvl, ssz;
    vector<array<int,L>> dp;
    
    vector<vector<int>> adj; 
    
    lca(int n) : n(n), lg(ceil(log2(n))), par(n, -1), lvl(n), ssz(n), dp(n), adj(n) {} 
    
    void add_edge(int x, int y) {
        adj[x].pb(y);
        adj[y].pb(x);
    }
    
    void dfs(int x) {
        ssz[x]=1;
        
        for(auto i:adj[x]) {
            if(!ssz[i]) {
                par[i]=x;
                lvl[i]=lvl[x]+1;
                dfs(i);
                ssz[x]+=ssz[i];
            }
        }
    }
    
    void init(int root=0) {
        dfs(root);
        for(int i=1;i<n;++i) {
            fill(all(dp[i]), -1);
        }
        
        for(int i=1;i<n;++i) {
            dp[i][0]=par[i];
        }
        
        for(int j=1;j<lg;++j) {
            for(int i=1;i<n;++i) {

                if(dp[i][j-1]!=-1) {
                    dp[i][j]=dp[dp[i][j-1]][j-1];
                }
            }
        }
    }
    
    int query(int p, int q) {
        if(p==q) return p;
        if(lvl[p]>lvl[q]) swap(p,q);
        
        for(int i=lg-1;i>=0;i--) {
            if(dp[q][i]!=-1 && lvl[p]<=lvl[dp[q][i]]) q=dp[q][i];
        }
        
        if(p==q) return p;
        
        for(int i=lg-1;i>=0;i--) {
            if(dp[q][i]!=-1 && dp[q][i]!=dp[p][i]) {
                p=dp[p][i];
                q=dp[q][i];
            }
        }
        
        return dp[p][0];
    }

    pair<int,int> query2(int& a, int& b) {
        int p=a, q=b;
        if(lvl[p]>lvl[q]){
             swap(p,q);
             swap(a,b);
         }
        for(int i=lg-1;i>=0;i--) {
            if(dp[q][i]!=-1 && lvl[p]<lvl[dp[q][i]]) q=dp[q][i];
        }
        
        if(lvl[p]!=lvl[q]) {
            if(p==par[q]) return {q,q};
            q=par[q];
        }
        
        assert(lvl[p]==lvl[q]);
        for(int i=lg-1;i>=0;i--) {
            if(dp[q][i]!=-1 && dp[q][i]!=dp[p][i]) {
                p=dp[p][i];
                q=dp[q][i];
            }
        }
        
        return {p,q};
    }

    int kth(int p, int k) {
        for(int i=0;i<lg;++i) {
            if(k&(1<<i)) {
                p=dp[p][i];
            }
        }
        
        return p;
    }

    int dist(int a, int b) {
        int l=query(a,b);
        return lvl[a]+lvl[b]-2*lvl[l];
    }

};


const int LG=17;
int n,m;
//~ vector<int> ord;
void dfs(int x, int& cnt, vector<int>& indeg, vector<vector<int>>& adj, vector<bool>& volt) {
    cnt++;
    volt[x]=1;
    //~ if(x<m) ord.push_back(x);
    for(auto i:adj[x]) {
        indeg[i]--;
        if(indeg[i]==0) dfs(i, cnt, indeg, adj, volt);
    }
}

int main() {
    IO;
    int T, csind=0;
    cin>>T;
    while(T--) {
        csind++;
        cin>>n;
        lca<LG> l(n+1);
        for(int i=1;i<n;++i) {
            int a,b;
            cin>>a>>b;
            //~ a=i;
            //~ b=i+1;
            l.add_edge(a, b);
        }
        
        l.init(1);
        
        cin>>m;
        vector<pair<int,int>> lst(m);
        for(int i=0;i<m;++i) {
            cin>>lst[i].xx>>lst[i].yy;
        }
    
        
        vector<array<pair<int,int>,LG>> idx(n+1);
        int nxt=m;
        for(int i=1;i<=n;++i) {
            for(int j=0;j<LG;++j) {
                idx[i][j].xx=nxt++;
                idx[i][j].yy=nxt++;
            }
        }
        
        vector<vector<int>> adj(nxt);
        vector<int> indeg(nxt);
        auto add_edge=[&](int a, int b, bool rev=false) {
            if(rev) swap(a,b);
            indeg[b]++;
            adj[a].pb(b);
            //~ cerr<<a<<" "<<b<<"\n";
        };
        
        for(int i=1;i<=n;++i) {
            for(int j=1;j<LG;++j) {
                if(l.dp[i][j-1]!=-1) add_edge(idx[l.dp[i][j-1]][j-1].xx, idx[i][j].xx);
                add_edge(idx[i][j-1].xx, idx[i][j].xx);
                if(l.dp[i][j-1]!=-1) add_edge(idx[l.dp[i][j-1]][j-1].yy, idx[i][j].yy, true);
                add_edge(idx[i][j-1].yy, idx[i][j].yy, true);
            }
        }
        //~ LOG("here");
        for(int i=0;i<m;++i) {
            int from=lst[i].xx, to=lst[i].yy;
            
            //~ cerr<<i<<" "<<idx[from][0].yy<<"\n";
            add_edge(i, idx[from][0].xx);
            add_edge(idx[to][0].yy, i);
            
        
            int os=l.query(from, to);
            if(os!=from) {
                from=l.par[from];
            }else {
                from=l.query2(from, to).yy;
            }
            os=l.query(from, to);
 
            for(int j=LG-1;j>=0;j--) {
                if(l.dp[from][j]!=-1 && l.lvl[l.dp[from][j]]>=l.lvl[os]) {
                    add_edge(idx[from][j].xx, i);
                    from=l.dp[from][j];
                }
            }
            for(int j=LG-1;j>=0;j--) {
                if(l.dp[to][j]!=-1 && l.lvl[l.dp[to][j]]>=l.lvl[os]) {
                    add_edge(idx[to][j].xx, i);
                    to=l.dp[to][j];
                }
            }

            
            add_edge(idx[os][0].xx, i);
            
            from=lst[i].xx; to=lst[i].yy;
            os=l.query(from, to);
            if(os!=to) {
                to=l.par[to];
            }else {
                to=l.query2(to, from).yy;
            }
            //~ cerr<<from<<" "<<to<<"??\n";
            os=l.query(from, to);
            for(int j=LG-1;j>=0;j--) {
                if(l.dp[from][j]!=-1 && l.lvl[l.dp[from][j]]>=l.lvl[os]) {
                    add_edge(idx[from][j].yy, i, true);
                    from=l.dp[from][j];
                }
            }
            for(int j=LG-1;j>=0;j--) {
                if(l.dp[to][j]!=-1 && l.lvl[l.dp[to][j]]>=l.lvl[os]) {
                    add_edge(idx[to][j].yy, i, true);
                    to=l.dp[to][j];
                }
            }
            add_edge(idx[os][0].yy, i, true);            
        }
        
        vector<bool> volt(nxt);
        int cnt=0;
        for(int i=0;i<nxt;++i) {
            if(indeg[i]==0 && !volt[i]) dfs(i, cnt, indeg, adj, volt);
        }
        //~ for(auto i:ord) cerr<<i<<" ";cerr<<"\n";
        
        //~ LOG(cnt);
        cout<<(cnt==nxt?"Yes":"No")<<"\n";
        
        
    }
    return 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