Submission #993937

#	Time	Username	Problem	Language	Result	Execution time	Memory
993937		Peti	Jail (JOI22_jail)	C++17	72 / 100	2062 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