Submission #862248

#	Time	Username	Problem	Language	Result	Execution time	Memory
862248		lolismek	Jail (JOI22_jail)	C++14	0 / 100	23 ms	110028 KiB

jail

#include <iostream>
#include <vector>

#define pii pair <int, int>

using namespace std;

const int NMAX = 120000;
const int LG = 17;

vector <int> adj[NMAX + 1];
pii ch[NMAX + 1];

int lvl[NMAX + 1];
int par[NMAX + 1][LG + 1];

int id1[NMAX + 1][LG + 1];
int id2[NMAX + 1][LG + 1];

void dfs(int node, int parent){
    lvl[node] = lvl[parent] + 1;
    par[node][0] = parent;

    for(int child : adj[node]){
        if(child != parent){
            dfs(child, node);
        }
    }
}

vector <int> G[2 * LG * NMAX + NMAX + 1];

int LCA(int a, int b){
    if(lvl[a] < lvl[b]){
        swap(a, b);
    }

    int diff = lvl[a] - lvl[b];
    for(int i = LG; i >= 0; i--){
        if((1 << i) & diff){
            a = par[a][i];
        }
    }

    if(a == b){
        return a;
    }

    for(int i = LG; i >= 0; i--){
        if(par[a][i] != par[b][i]){
            a = par[a][i];
            b = par[b][i];
        }
    }

    return par[a][0];
}

int stat[2 * LG * NMAX + NMAX + 1];

bool cyc = false;
void dfsg(int node){
    stat[node] = 1;

    for(int vec : G[node]){
        if(stat[vec] == 0){
            dfsg(vec);
        }else if(stat[vec] == 1){
            cyc = true;
        }
    }

    stat[node] = 2;
}

void solve(){
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++){
        adj[i].clear();
    }

    for(int i = 1; i <= n - 1; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    int m;
    cin >> m;

    for(int i = 1; i <= m; i++){
        cin >> ch[i].first >> ch[i].second;
    }

    dfs(1, 0);

    for(int j = 1; (1 << j) <= n; j++){
        for(int i = 1; i <= n; i++){
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }

    int lbl = m;
    for(int i = 1; i <= n; i++){
        for(int j = 0; (1 << j) <= lvl[i]; j++){
            id1[i][j] = ++lbl;
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 0; (1 << j) <= lvl[i]; j++){
            id2[i][j] = ++lbl;
        }
    }

    for(int i = 1; i <= lbl; i++){
        G[i].clear();
    }

    // type 1
    for(int i = 1; i <= n; i++){
        for(int j = 1; (1 << j) <= lvl[i]; j++){
            G[id1[i][j - 1]].push_back(id1[i][j]);
            G[id1[par[i][j - 1]][j - 1]].push_back(id1[i][j]);
        }
    }

    //type 2
    for(int i = 1; i <= n; i++){
        for(int j = 1; (1 << j) <= lvl[i]; j++){
            G[id2[i][j]].push_back(id2[i][j - 1]);
            G[id2[i][j]].push_back(id2[par[i][j - 1]][j - 1]);
        }
    }

    for(int i = 1; i <= m; i++){
        int lca = LCA(ch[i].first, ch[i].second);

        // type 1
        G[i].push_back(id1[ch[i].first][0]);

        int node = ch[i].first;
        for(int j = LG; j >= 0; j--){
            if(lvl[par[node][j]] >= lvl[lca]){
                G[id1[node][j]].push_back(i);
                node = par[par[node][j]][0];
            }
        }
        node = ch[i].second;
        for(int j = LG; j >= 0; j--){
            if(lvl[par[node][j]] >= lvl[lca]){
                G[id1[node][j]].push_back(i);
                node = par[par[node][j]][0];
            }
        }

        // type 2
        G[id2[ch[i].second][0]].push_back(i);

        node = ch[i].first;
        for(int j = LG; j >= 0; j--){
            if(lvl[par[node][j]] >= lvl[lca]){
                G[i].push_back(id2[node][j]);
                node = par[par[node][j]][0];
            }
        }
        node = ch[i].second;
        for(int j = LG; j >= 0; j--){
            if(lvl[par[node][j]] >= lvl[lca]){
                G[i].push_back(id2[node][j]);
                node = par[par[node][j]][0];
            }
        }
    }

    for(int i = 1; i <= lbl; i++){
        stat[i] = 0;
    }

    cyc = false;
    for(int i = 1; i <= lbl && !cyc; i++){
        if(stat[i] == 0){
            dfsg(i);
        }
    }

    if(cyc){
        cout << "No\n";
    }else{
        cout << "Yes\n";
    }
}

int main(){

    int T;
    cin >> T;

    while(T--){
        solve();
    }

    return 0;
}

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