Submission #994096

#	Time	Username	Problem	Language	Result	Execution time	Memory
994096		vjudge1	Jail (JOI22_jail)	C++17	72 / 100	2035 ms	1048576 KiB

jail

#include <bits/stdc++.h>
 
using namespace std;
 
const int logn = 20;
 
vector<vector<int>> g, idxs, g2;
 
vector<vector<int>> lca;
vector<int> in, out;
 
inline bool parent(int a, int b) { return in[a] <= in[b] && out[b] <= out[a]; }
 
int get_lca(int a, int b){
    if(parent(a, b)) return a;
    for(int i = logn-1; i >= 0; i--){
        if(!parent(lca[a][i], b)){
            a = lca[a][i];
        }
    }
    return lca[a][0];
}
 
int ido = 0;
void dfs(int x, int p){
    lca[x][0] = p;
    in[x] = ido++;
    for(int y : g[x]){
        if(y != p){
            dfs(y, x);
        }
    }
    out[x] = ido++;
}
 
void walk_up(int a, int c, int idx){
    while(a != c){
        idxs[a].push_back(idx);
        a = lca[a][0];
    }
}
 
void update(int a, int b, int idx){
    int c = get_lca(a,  b);
    walk_up(a, c, idx);
    walk_up(b, c, idx);
    idxs[c].push_back(idx);
}
 
vector<bool> vis, done;
bool dfs2(int x){
    vis[x] = true;
    bool res = true;
    for(int y : g2[x]){
        if(!vis[y]){
            res = res && dfs2(y);
        } else if(!done[y]){
            return false;
        }
    }
    done[x] = true;
    return res;
}
 
void solve(){
    int n;
    cin>>n;
 
    g.assign(n, vector<int>());
    idxs.assign(n, vector<int>());
    for(int i = 0; i < n-1; i++){
        int a, b;
        cin>>a>>b;
        --a, --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
 
    lca.assign(n, vector<int>(logn, 0));
    in.assign(n, 0);
    out.assign(n, 0);
    ido = 0;
    dfs(0, 0);
    for(int j = 1; j < 20; j++){
        for(int i = 0; i < n; i++){
            lca[i][j] = lca[lca[i][j-1]][j-1];
        }
    }
 
    int m;
    cin>>m;
    vector<pair<int, int>> query(m);
    g2.assign(m, vector<int>());
    for(int i = 0; i < m; i++){
        int a, b;
        cin>>a>>b;
        --a, --b;
        query[i] = {a, b};
 
        update(a, b, i);
    }
 
    for(int i = 0; i < m; i++){
        for(int x : idxs[query[i].first]){
            if(i != x) g2[x].push_back(i);
        }
        for(int x : idxs[query[i].second]){
            if(i != x) g2[i].push_back(x);
        }
    }
 
    vis.assign(m, false);
    done.assign(m, false);
    bool ok = true;
    for(int i = 0; i < m; i++){
        if(!vis[i]){
            ok = ok && dfs2(i);
        }
    }
 
    cout << (ok ? "Yes" : "No") <<'\n';
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
    cin>>t;
    while(t--) solve();
 
    return 0;
}

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