Submission #863646

#	Time	Username	Problem	Language	Result	Execution time	Memory
863646		lolismek	Jail (JOI22_jail)	C++14	100 / 100	1508 ms	358672 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++){
        //cout << "** " << i << endl;
        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((1 << j ) <= lvl[node] && lvl[par[node][j]] + 1 >= lvl[lca]){
                    G[id1[node][j]].push_back(i);
                    //cout << 1 << ' ' << node << ' ' << j << ' ' << node << endl;
                    node = par[node][j];
                }
            }
        }
        node = ch[i].second;
        for(int j = LG; j >= 0; j--){
            if((1 << j ) <= lvl[node] && lvl[par[node][j]] + 1 > lvl[lca]){
                G[id1[node][j]].push_back(i);
                //cout << 2 << ' ' << node << ' ' << j << ' ' << node << endl;
                node = par[node][j];
            }
        }

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

        node = ch[i].first;
        for(int j = LG; j >= 0; j--){
            if((1 << j ) <= lvl[node] && lvl[par[node][j]] + 1 > lvl[lca]){
                G[i].push_back(id2[node][j]);
                //cout << 3 << ' ' << node << ' ' << j << ' ' << node << endl;
                node = par[node][j];
            }
        }
        node = par[ch[i].second][0];
        if(node != 0){
            for(int j = LG; j >= 0; j--){
                if((1 << j ) <= lvl[node] && lvl[par[node][j]] + 1 >= lvl[lca]){
                    G[i].push_back(id2[node][j]);
                    //cout << 4 << ' ' << node << ' ' << j << ' ' << node << endl;
                    node = par[node][j];
                }
            }
        }
    }

    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;
}

/*
1
15
1 2
2 4
2 5
4 6
4 7
5 8
5 9
1 3
3 10
3 11
10 12
10 13
11 14
11 15
4
10 11
1 12
6 15
1 11

1
15
1 2
2 4
2 5
4 6
4 7
5 8
5 9
1 3
3 10
3 11
10 12
10 13
11 14
11 15
2
6 15
1 11

1
4
1 2
2 3
3 4
2
1 4
2 3
are ciclu!!!
*/

• 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