Submission #710852

#	Time	Username	Problem	Language	Result	Execution time	Memory
710852		Darren0724	Jail (JOI22_jail)	C++17	100 / 100	1318 ms	287696 KiB

jail

#include<bits/stdc++.h>
using namespace std;
const int N=120005;
const int K=18;
int n,m;
vector<vector<int>> adj;
vector<vector<int>> g;
vector<vector<int>> jump(K,vector<int>(N));
vector<int> deep(N);
vector<int> s1;
vector<int> t1;
void dfs(int k,int pa){
    jump[0][k]=pa;
    for(int i=1;i<K;i++){
        jump[i][k]=jump[i-1][jump[i-1][k]];
    }
    for(int j:adj[k]){
        if(j==pa){
            continue;
        }
        deep[j]=deep[k]+1;
        dfs(j,k);
    }
}
int lca(int a,int b){
    if(deep[a]<deep[b]){
        swap(a,b);
    }
    int d=deep[a]-deep[b];
    for(int i=0;i<K;i++){
        if((1<<i)&d){
            a=jump[i][a];
        }
    }
    if(a==b){
        return b;
    }
    for(int i=K-1;i>=0;i--){
        if(jump[i][a]!=jump[i][b]){
            a=jump[i][a];
            b=jump[i][b];
        }
    }
    return jump[0][a];
}
int num1(int a,int b){
    return m+b*n+a;
}
int num2(int a,int b){
    return m+(b+K)*n+a;
}
void add1(int from,int to,int dis){
    if(dis==-1){
        return;
    }
    for(int i=0;i<K;i++){
        if(dis&(1<<i)){
            g[from].push_back(num1(to,i));
            to=jump[i][to];
        }
    }
}
void add2(int to,int from,int dis){
    if(dis==-1){
        return;
    }
    for(int i=0;i<K;i++){
        if(dis&(1<<i)){
            g[num2(from,i)].push_back(to);
            from=jump[i][from];
        }
    }
}
void solve(){
    adj.clear();
    g.clear();
    s1.resize(0);
    t1.resize(0);
    cin>>n;
    adj.resize(n);
    s1.resize(n,-1);
    t1.resize(n,-1);

    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;a--;b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(0,0);
    cin>>m;
    int N=num2(n-1,K-1)+1;
    g.resize(N);
    vector<int> s(m),t(m);
    for(int i=0;i<m;i++){
        cin>>s[i]>>t[i];s[i]--;t[i]--;
        s1[s[i]]=i;
        t1[t[i]]=i;
    }
    for(int i=0;i<m;i++){
        int l=lca(s[i],t[i]);
        add1(i,jump[0][s[i]],deep[s[i]]-deep[l]);
        add1(i,t[i],deep[t[i]]-deep[l]);
    }
    for(int i=0;i<m;i++){
        int l=lca(s[i],t[i]);
        add2(i,s[i],deep[s[i]]-deep[l]);
        add2(i,jump[0][t[i]],deep[t[i]]-deep[l]);
    }
    for(int j=K-1;j>0;j--){
        for(int i=0;i<n;i++){
            g[num1(i,j)].push_back(num1(i,j-1));
            g[num1(i,j)].push_back(num1(jump[j-1][i],j-1));
        }
    }
    for(int j=K-1;j>0;j--){
        for(int i=0;i<n;i++){
            g[num2(i,j-1)].push_back(num2(i,j));
            g[num2(jump[j-1][i],j-1)].push_back(num2(i,j));
        }
    }
    for(int i=0;i<n;i++){
        if(s1[i]!=-1){
            g[num1(i,0)].push_back(s1[i]);
        }
        if(t1[i]!=-1){
            g[t1[i]].push_back(num2(i,0));
        }
    }
    vector<int> in(N);
    for(int i=0;i<N;i++){
        for(int j:g[i]){
            in[j]++;
        }
    }
    queue<int> q;
    for(int i=0;i<N;i++){
        if(in[i]==0){
            q.push(i);
        }
    }
    int cnt=0;
    while(q.size()){
        int p=q.front();
        q.pop();
        cnt++;
        for(int j:g[p]){
            in[j]--;
            if(in[j]==0){
                q.push(j);
            }
        }
    }
    if(cnt==N){
        cout<<"Yes"<<'\n';
    }
    else{
        cout<<"No"<<'\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }

    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