oj.uz

Submission #567742

# Submission time Handle Problem Language Result Execution time Memory
567742 2022-05-24T06:20:37 Z joshjms Jail (JOI22_jail) C++14
5 / 100
 2228 ms 439412 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[4800005];

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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 115788 KB Output is correct
2 Correct 53 ms 115904 KB Output is correct
3 Correct 54 ms 115820 KB Output is correct
4 Correct 108 ms 124568 KB Output is correct
5 Correct 181 ms 132916 KB Output is correct
6 Correct 60 ms 117008 KB Output is correct
7 Correct 60 ms 117004 KB Output is correct
8 Correct 63 ms 117076 KB Output is correct
9 Correct 407 ms 137708 KB Output is correct
10 Correct 851 ms 352232 KB Output is correct
11 Correct 80 ms 120264 KB Output is correct
12 Correct 218 ms 133600 KB Output is correct
13 Correct 1183 ms 368328 KB Output is correct
14 Correct 1204 ms 368432 KB Output is correct
15 Correct 1703 ms 389700 KB Output is correct
16 Correct 2228 ms 439412 KB Output is correct
17 Correct 1263 ms 399636 KB Output is correct
18 Correct 1133 ms 366420 KB Output is correct
19 Correct 1214 ms 375896 KB Output is correct
20 Correct 1091 ms 384304 KB Output is correct
21 Correct 1356 ms 395152 KB Output is correct
22 Correct 968 ms 359372 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 115788 KB Output is correct
2 Correct 53 ms 115904 KB Output is correct
3 Correct 63 ms 116964 KB Output is correct
4 Incorrect 65 ms 117004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 115788 KB Output is correct
2 Correct 53 ms 115904 KB Output is correct
3 Correct 63 ms 116964 KB Output is correct
4 Incorrect 65 ms 117004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 115788 KB Output is correct
2 Correct 53 ms 115904 KB Output is correct
3 Correct 63 ms 116964 KB Output is correct
4 Incorrect 65 ms 117004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 115788 KB Output is correct
2 Correct 53 ms 115904 KB Output is correct
3 Correct 63 ms 116964 KB Output is correct
4 Incorrect 65 ms 117004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 115788 KB Output is correct
2 Correct 58 ms 115924 KB Output is correct
3 Correct 62 ms 115844 KB Output is correct
4 Correct 57 ms 115896 KB Output is correct
5 Correct 79 ms 120136 KB Output is correct
6 Correct 57 ms 117032 KB Output is correct
7 Correct 57 ms 117052 KB Output is correct
8 Incorrect 56 ms 116024 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 115788 KB Output is correct
2 Correct 53 ms 115904 KB Output is correct
3 Correct 54 ms 115820 KB Output is correct
4 Correct 108 ms 124568 KB Output is correct
5 Correct 181 ms 132916 KB Output is correct
6 Correct 60 ms 117008 KB Output is correct
7 Correct 60 ms 117004 KB Output is correct
8 Correct 63 ms 117076 KB Output is correct
9 Correct 407 ms 137708 KB Output is correct
10 Correct 851 ms 352232 KB Output is correct
11 Correct 80 ms 120264 KB Output is correct
12 Correct 218 ms 133600 KB Output is correct
13 Correct 1183 ms 368328 KB Output is correct
14 Correct 1204 ms 368432 KB Output is correct
15 Correct 1703 ms 389700 KB Output is correct
16 Correct 2228 ms 439412 KB Output is correct
17 Correct 1263 ms 399636 KB Output is correct
18 Correct 1133 ms 366420 KB Output is correct
19 Correct 1214 ms 375896 KB Output is correct
20 Correct 1091 ms 384304 KB Output is correct
21 Correct 1356 ms 395152 KB Output is correct
22 Correct 968 ms 359372 KB Output is correct
23 Correct 53 ms 115788 KB Output is correct
24 Correct 53 ms 115904 KB Output is correct
25 Correct 63 ms 116964 KB Output is correct
26 Incorrect 65 ms 117004 KB Output isn't correct
27 Halted 0 ms 0 KB -