oj.uz

Submission #863614

# Submission time Handle Problem Language Result Execution time Memory
863614 2023-10-20T15:47:14 Z lolismek Jail (JOI22_jail) C++14
0 / 100
 26 ms 110088 KB 
#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 = par[ch[i].first][0];
        if(node != 0){
            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 = par[ch[i].second][0];
        if(node != 0){
            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;
}

/*
2
7
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7
4
1 2
1 3
1 4
3
2 3
3 4
4 2
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 109916 KB Output is correct
2 Correct 23 ms 109884 KB Output is correct
3 Incorrect 23 ms 109916 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 110088 KB Output is correct
2 Incorrect 22 ms 109912 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 110088 KB Output is correct
2 Incorrect 22 ms 109912 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 110088 KB Output is correct
2 Incorrect 22 ms 109912 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 110088 KB Output is correct
2 Incorrect 22 ms 109912 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 109904 KB Output is correct
2 Correct 23 ms 109916 KB Output is correct
3 Correct 23 ms 109916 KB Output is correct
4 Incorrect 22 ms 109916 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 109916 KB Output is correct
2 Correct 23 ms 109884 KB Output is correct
3 Incorrect 23 ms 109916 KB Output isn't correct
4 Halted 0 ms 0 KB -