oj.uz

Submission #567741

# Submission time Handle Problem Language Result Execution time Memory
567741 2022-05-24T06:19:48 Z joshjms Jail (JOI22_jail) C++17
0 / 100
 672 ms 478068 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")

#define int long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << "\n";

const long long mod = 1e9 + 7;

int n, a[120005], b[120005], m, s[120005], t[120005];
vector <int> g[120005];

int par[120005][20], in[120005], out[120005], tmr;
int node[120005][20][2], nodes;

vector <int> dirGraph[2400005];

int vis[4800005], flag;

void init() {
    cin >> n;
    for(int i = 1; i < n; i++)
        cin >> a[i] >> b[i];

    cin >> m;
    for(int i = 1; i <= m; i++)
        cin >> s[i] >> t[i];

    for(int i = 1; i <= n; i++) {
        g[i].clear();
        in[i] = out[i] = 0;
        for(int j = 0; j < 20; j++) par[i][j] = 0;
    }

    for(int i = 1; i < n; i++) {
        g[a[i]].pb(b[i]);
        g[b[i]].pb(a[i]);
    }

    in[0] = -1;
    out[0] = 1e18;

    tmr = 0;

    for(int i = 1; i <= 40 * n; i++) {
        dirGraph[i].clear();
        vis[i] = 0;
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 20; j++) {
            node[i][j][0] = node[i][j][1] = 0;
        }
    }
    nodes = 0;
}

void dfs(int v, int p) {
    par[v][0] = v;
    par[v][1] = p;

    for(int i = 2; i < 18; i++) 
        par[v][i] = par[par[par[v][i - 1]][1]][i - 1];

    in[v] = ++tmr;

    for(auto c : g[v]) if(c != p) 
        dfs(c, v);

    out[v] = ++tmr;
}

void findCycle(int v) {
    vis[v] = 1;
    for(auto c : dirGraph[v]) {
        if(vis[c] == 1) {flag = 1; return;}
        if(vis[c] == 0) findCycle(c);
    }
    vis[v] = 2;
}

void solve () {
    dfs(1, 0);

    // for(int i = 1; i <= n; i++) {
    //     for(int j = 0; j < 18; j++) {
    //         cout << par[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    nodes = 0;

    for(int i = 1; i <= n; i++) {
        node[i][0][0] = ++nodes;
        node[i][0][1] = ++nodes;
    }

    for(int i = 1; i <= m; i++) {
        dirGraph[node[s[i]][0][0]].pb(node[t[i]][0][1]);
    }
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < 18; j++) {
            node[i][j][0] = ++nodes;
            node[i][j][1] = ++nodes;

            // cout << "[" << i << " " << j << "] => " << node[i][j][0] << ", " << node[i][j][1] << "\n";

            dirGraph[node[i][j][0]].pb(node[i][j - 1][0]);
            if(dirGraph[node[i][j][0]].back() == 0) dirGraph[node[i][j][0]].pop_back();
            dirGraph[node[i][j][0]].pb(node[par[par[i][j - 1]][1]][j - 1][0]);
            if(dirGraph[node[i][j][0]].back() == 0) dirGraph[node[i][j][0]].pop_back();

            dirGraph[node[i][j - 1][1]].pb(node[i][j][1]);
            if(dirGraph[node[i][j - 1][1]].back() == 0) dirGraph[node[i][j - 1][1]].pop_back();
            dirGraph[node[par[par[i][j - 1]][1]][j - 1][1]].pb(node[i][j][1]);
            if(dirGraph[node[i][j - 1][1]].back() == 0) dirGraph[node[i][j - 1][1]].pop_back();
        }
    }

    auto lca = [&](int u, int v) {
        if(in[u] <= in[v] && out[u] >= out[v]) return u;
        if(in[v] <= in[u] && out[v] >= out[u]) return v;
        for(int i = 17; i >= 0; i--) {
            if(in[par[u][i]] <= in[v] && out[par[u][i]] >= out[v]) continue;
            u = par[u][i];
        }
        return par[u][1];
    };

    for(int i = 1; i <= m; i++) {
        int LCA = lca(s[i], t[i]);

        // debug(s[i]);
        // debug(t[i]);

        // debug(LCA);

        if(LCA == s[i]) {
            int u, v;

            u = t[i], v = s[i];
            for(int j = 17; j >= 0; j--) {
                if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue;
                dirGraph[node[s[i]][0][0]].pb(node[u][j][0]);
                // cout << "connect [" << u << " " << i << "]\n"; 
                // debug(s[i]);
                // debug(node[s[i]][0][0]);
                // debug(node[u][i][0]);
                u = par[par[u][j]][1];
            }

            u = par[t[i]][1], v = par[s[i]][1];
            for(int j = 17; j >= 0; j--) {
                if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue;
                dirGraph[node[u][j][1]].pb(node[s[i]][0][0]);
                // cout << "connect [" << u << " " << i << "]\n"; 
                u = par[par[u][j]][1];
            }
        }
        else if(LCA == t[i]) {
            int u, v;

            u = par[s[i]][1], v = par[t[i]][1];
            for(int j = 17; j >= 0; j--) {
                if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue;
                dirGraph[node[s[i]][0][0]].pb(node[u][j][0]);
                u = par[par[u][j]][1];
            }

            u = s[i], v = t[i];
            for(int j = 17; j >= 0; j--) {
                if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue;
                dirGraph[node[u][j][1]].pb(node[s[i]][0][0]);
                u = par[par[u][j]][1];
            }
        }
        else {
            int u, v;

            u = par[s[i]][1], v = par[LCA][1];
            for(int j = 17; j >= 0; j--) {
                if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue;
                dirGraph[node[s[i]][0][0]].pb(node[u][j][0]);
                u = par[par[u][j]][1];
            }

            u = t[i], v = par[LCA][1];
            for(int j = 17; j >= 0; j--) {
                if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue;
                dirGraph[node[s[i]][0][0]].pb(node[u][j][0]);
                u = par[par[u][j]][1];
            }

            u = par[t[i]][1], v = par[LCA][1];
            for(int j = 17; j >= 0; j--) {
                if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue;
                dirGraph[node[u][j][1]].pb(node[s[i]][0][0]);
                u = par[par[u][j]][1];
            }

            u = s[i], v = par[LCA][1];
            for(int j = 17; j >= 0; j--) {
                if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue;
                dirGraph[node[u][j][1]].pb(node[s[i]][0][0]);
                u = par[par[u][j]][1];
            }
        }
    }

    // for(int i = 1; i <= nodes; i++) {
    //     debug(i);
    //     for(auto c : dirGraph[i])
    //         cout << c << " ";
    //     cout << "\n";
    // }

    flag = 0;

    for(int i = 1; i <= n; i++) {
        if(vis[node[i][0][0]] == 0) {
            findCycle(node[i][0][0]);
            
            if(flag) break;
        }
    }

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

signed main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tc; cin >> tc;
    while(tc--) {
        init ();
        solve ();
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 59444 KB Output is correct
2 Correct 30 ms 59484 KB Output is correct
3 Correct 39 ms 59464 KB Output is correct
4 Correct 93 ms 68396 KB Output is correct
5 Correct 154 ms 76848 KB Output is correct
6 Correct 37 ms 60744 KB Output is correct
7 Correct 41 ms 60728 KB Output is correct
8 Correct 38 ms 60684 KB Output is correct
9 Correct 389 ms 81972 KB Output is correct
10 Runtime error 672 ms 478068 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 59476 KB Output is correct
2 Correct 39 ms 59516 KB Output is correct
3 Correct 46 ms 60656 KB Output is correct
4 Incorrect 40 ms 60636 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 59476 KB Output is correct
2 Correct 39 ms 59516 KB Output is correct
3 Correct 46 ms 60656 KB Output is correct
4 Incorrect 40 ms 60636 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 59476 KB Output is correct
2 Correct 39 ms 59516 KB Output is correct
3 Correct 46 ms 60656 KB Output is correct
4 Incorrect 40 ms 60636 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 59476 KB Output is correct
2 Correct 39 ms 59516 KB Output is correct
3 Correct 46 ms 60656 KB Output is correct
4 Incorrect 40 ms 60636 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 59472 KB Output is correct
2 Correct 31 ms 59524 KB Output is correct
3 Correct 36 ms 59460 KB Output is correct
4 Correct 34 ms 59528 KB Output is correct
5 Correct 66 ms 63868 KB Output is correct
6 Correct 36 ms 60692 KB Output is correct
7 Correct 37 ms 60720 KB Output is correct
8 Incorrect 31 ms 59552 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 59444 KB Output is correct
2 Correct 30 ms 59484 KB Output is correct
3 Correct 39 ms 59464 KB Output is correct
4 Correct 93 ms 68396 KB Output is correct
5 Correct 154 ms 76848 KB Output is correct
6 Correct 37 ms 60744 KB Output is correct
7 Correct 41 ms 60728 KB Output is correct
8 Correct 38 ms 60684 KB Output is correct
9 Correct 389 ms 81972 KB Output is correct
10 Runtime error 672 ms 478068 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -