oj.uz

Submission #941650

# Submission time Handle Problem Language Result Execution time Memory
941650 2024-03-09T08:36:56 Z alextodoran Jail (JOI22_jail) C++17
49 / 100
 290 ms 328068 KB 
/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 120000;
const int M_MAX = N_MAX;
const int LOG_N = 17;
const int V_MAX = M_MAX + N_MAX * LOG_N;

int Q;

int N;
vector <int> adj[N_MAX + 2];
int M;
int start[M_MAX + 2], finish[M_MAX + 2];

int parent[N_MAX + 2];
int depth[N_MAX + 2];

void dfs (int u) {
    for (int v : adj[u]) {
        if (v != parent[u]) {
            parent[v] = u;
            depth[v] = depth[u] + 1;
            dfs(v);
        }
    }
}

int start_id[N_MAX + 2], finish_id[N_MAX + 2];

int V;
vector <int> out[V_MAX + 2];
int deg[V_MAX + 2];

void add_edge (int u, int v) {
    out[u].push_back(v);
    deg[v]++;
}

int anc[N_MAX + 2][LOG_N];
int seg_out[N_MAX + 2][LOG_N];
int seg_in[N_MAX + 2][LOG_N];

void build () {
    for (int u = 1; u <= N; u++) {
        anc[u][0] = parent[u];
    }
    for (int k = 1; k < LOG_N; k++) {
        for (int u = 1; u <= N; u++) {
            anc[u][k] = anc[anc[u][k - 1]][k - 1];
        }
    }
    V = M;
    for (int u = 1; u <= N; u++) {
        seg_out[u][0] = ++V;
        seg_in[u][0] = ++V;
        if (finish_id[u] != 0) {
            add_edge(seg_out[u][0], finish_id[u]);
        }
        if (start_id[u] != 0) {
            add_edge(start_id[u], seg_in[u][0]);
        }
    }
    for (int k = 1; k < LOG_N; k++) {
        for (int u = 1; u <= N; u++) {
            seg_out[u][k] = ++V;
            seg_in[u][k] = ++V;
            add_edge(seg_out[u][k], seg_out[u][k - 1]);
            add_edge(seg_in[u][k - 1], seg_in[u][k]);
            if (anc[u][k - 1] != 0) {
                add_edge(seg_out[u][k], seg_out[anc[u][k - 1]][k - 1]);
                add_edge(seg_in[anc[u][k - 1]][k - 1], seg_in[u][k]);
            }
        }
    }
}

int ancestor (int u, int len) {
    for (int k = 0; k < LOG_N; k++) {
        if ((len >> k) & 1) {
            u = anc[u][k];
        }
    }
    return u;
}

int lca (int u, int v) {
    if (depth[u] > depth[v]) {
        u = ancestor(u, depth[u] - depth[v]);
    }
    if (depth[v] > depth[u]) {
        v = ancestor(v, depth[v] - depth[u]);
    }
    if (u == v) {
        return u;
    }
    for (int k = LOG_N - 1; k >= 0; k--) {
        if (anc[u][k] != anc[v][k]) {
            u = anc[u][k];
            v = anc[v][k];
        }
    }
    return parent[u];
}

void add_path (int i, int u, int v) {
    int len = depth[u] - depth[v];
    for (int k = 0; k < LOG_N; k++) {
        if ((len >> k) & 1) {
            add_edge(i, seg_out[u][k]);
            add_edge(seg_in[u][k], i);
            u = anc[u][k];
        }
    }
}

void clean () {
    for (int u = 1; u <= N; u++) {
        adj[u].clear();
        parent[u] = 0;
        depth[u] = 0;
        start_id[u] = 0;
        finish_id[u] = 0;
    }
    for (int u = 1; u <= V; u++) {
        out[u].clear();
        deg[u] = 0;
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> Q;
    while (Q--) {
        cin >> N;
        for (int i = 1; i <= N - 1; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        dfs(1);
        cin >> M;
        for (int i = 1; i <= M; i++) {
            cin >> start[i] >> finish[i];
            start_id[start[i]] = i;
            finish_id[finish[i]] = i;
        }
        build();
        for (int i = 1; i <= M; i++) {
            int u = start[i], v = finish[i];
            int x = lca(u, v);
            if (u != x) {
                add_path(i, parent[u], x);
            }
            if (v != x) {
                add_path(i, parent[v], x);
            }
            if (finish_id[u] != 0) {
                add_edge(i, finish_id[u]);
            }
            if (start_id[v] != 0) {
                add_edge(start_id[v], i);
            }
            if (u != x && v != x) {
                if (finish_id[x] != 0) {
                    add_edge(i, finish_id[x]);
                }
                if (start_id[x] != 0) {
                    add_edge(start_id[x], i);
                }
            }
        }
        queue <int> q;
        for (int u = 1; u <= V; u++) {
            if (deg[u] == 0) {
                q.push(u);
            }
        }
        while (q.empty() == false) {
            int u = q.front();
            q.pop();
            for (int v : out[u]) {
                if (--deg[v] == 0) {
                    q.push(v);
                }
            }
        }
        bool ok = true;
        for (int u = 1; u <= V; u++) {
            if (deg[u] > 0) {
                ok = false;
                break;
            }
        }
        cout << (ok == true ? "Yes" : "No") << "\n";
        clean();
    }

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64336 KB Output is correct
2 Correct 13 ms 64348 KB Output is correct
3 Correct 13 ms 64436 KB Output is correct
4 Correct 39 ms 64684 KB Output is correct
5 Correct 65 ms 65300 KB Output is correct
6 Correct 17 ms 64600 KB Output is correct
7 Correct 16 ms 64756 KB Output is correct
8 Correct 18 ms 64604 KB Output is correct
9 Correct 108 ms 76628 KB Output is correct
10 Runtime error 290 ms 328068 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 64344 KB Output is correct
2 Correct 14 ms 64348 KB Output is correct
3 Correct 16 ms 64604 KB Output is correct
4 Correct 16 ms 64584 KB Output is correct
5 Correct 16 ms 64604 KB Output is correct
6 Correct 16 ms 64604 KB Output is correct
7 Correct 16 ms 64604 KB Output is correct
8 Correct 20 ms 64860 KB Output is correct
9 Correct 16 ms 64604 KB Output is correct
10 Correct 16 ms 64600 KB Output is correct
11 Correct 16 ms 64600 KB Output is correct
12 Correct 15 ms 64600 KB Output is correct
13 Correct 16 ms 64800 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 64344 KB Output is correct
2 Correct 14 ms 64348 KB Output is correct
3 Correct 16 ms 64604 KB Output is correct
4 Correct 16 ms 64584 KB Output is correct
5 Correct 16 ms 64604 KB Output is correct
6 Correct 16 ms 64604 KB Output is correct
7 Correct 16 ms 64604 KB Output is correct
8 Correct 20 ms 64860 KB Output is correct
9 Correct 16 ms 64604 KB Output is correct
10 Correct 16 ms 64600 KB Output is correct
11 Correct 16 ms 64600 KB Output is correct
12 Correct 15 ms 64600 KB Output is correct
13 Correct 16 ms 64800 KB Output is correct
14 Correct 13 ms 64348 KB Output is correct
15 Correct 13 ms 64344 KB Output is correct
16 Correct 18 ms 64628 KB Output is correct
17 Correct 20 ms 64604 KB Output is correct
18 Correct 20 ms 64604 KB Output is correct
19 Correct 14 ms 64348 KB Output is correct
20 Correct 17 ms 64604 KB Output is correct
21 Correct 16 ms 64716 KB Output is correct
22 Correct 16 ms 64604 KB Output is correct
23 Correct 13 ms 64344 KB Output is correct
24 Correct 13 ms 64348 KB Output is correct
25 Correct 17 ms 64604 KB Output is correct
26 Correct 15 ms 64604 KB Output is correct
27 Correct 17 ms 64628 KB Output is correct
28 Correct 14 ms 64340 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 64344 KB Output is correct
2 Correct 14 ms 64348 KB Output is correct
3 Correct 16 ms 64604 KB Output is correct
4 Correct 16 ms 64584 KB Output is correct
5 Correct 16 ms 64604 KB Output is correct
6 Correct 16 ms 64604 KB Output is correct
7 Correct 16 ms 64604 KB Output is correct
8 Correct 20 ms 64860 KB Output is correct
9 Correct 16 ms 64604 KB Output is correct
10 Correct 16 ms 64600 KB Output is correct
11 Correct 16 ms 64600 KB Output is correct
12 Correct 15 ms 64600 KB Output is correct
13 Correct 16 ms 64800 KB Output is correct
14 Correct 13 ms 64348 KB Output is correct
15 Correct 13 ms 64344 KB Output is correct
16 Correct 18 ms 64628 KB Output is correct
17 Correct 20 ms 64604 KB Output is correct
18 Correct 20 ms 64604 KB Output is correct
19 Correct 14 ms 64348 KB Output is correct
20 Correct 17 ms 64604 KB Output is correct
21 Correct 16 ms 64716 KB Output is correct
22 Correct 16 ms 64604 KB Output is correct
23 Correct 13 ms 64344 KB Output is correct
24 Correct 13 ms 64348 KB Output is correct
25 Correct 17 ms 64604 KB Output is correct
26 Correct 15 ms 64604 KB Output is correct
27 Correct 17 ms 64628 KB Output is correct
28 Correct 14 ms 64340 KB Output is correct
29 Correct 16 ms 64600 KB Output is correct
30 Correct 18 ms 64604 KB Output is correct
31 Correct 17 ms 64628 KB Output is correct
32 Correct 17 ms 64600 KB Output is correct
33 Correct 17 ms 64604 KB Output is correct
34 Correct 16 ms 64604 KB Output is correct
35 Correct 16 ms 64600 KB Output is correct
36 Correct 16 ms 64600 KB Output is correct
37 Correct 16 ms 64600 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 64344 KB Output is correct
2 Correct 14 ms 64348 KB Output is correct
3 Correct 16 ms 64604 KB Output is correct
4 Correct 16 ms 64584 KB Output is correct
5 Correct 16 ms 64604 KB Output is correct
6 Correct 16 ms 64604 KB Output is correct
7 Correct 16 ms 64604 KB Output is correct
8 Correct 20 ms 64860 KB Output is correct
9 Correct 16 ms 64604 KB Output is correct
10 Correct 16 ms 64600 KB Output is correct
11 Correct 16 ms 64600 KB Output is correct
12 Correct 15 ms 64600 KB Output is correct
13 Correct 16 ms 64800 KB Output is correct
14 Correct 13 ms 64348 KB Output is correct
15 Correct 13 ms 64344 KB Output is correct
16 Correct 18 ms 64628 KB Output is correct
17 Correct 20 ms 64604 KB Output is correct
18 Correct 20 ms 64604 KB Output is correct
19 Correct 14 ms 64348 KB Output is correct
20 Correct 17 ms 64604 KB Output is correct
21 Correct 16 ms 64716 KB Output is correct
22 Correct 16 ms 64604 KB Output is correct
23 Correct 13 ms 64344 KB Output is correct
24 Correct 13 ms 64348 KB Output is correct
25 Correct 17 ms 64604 KB Output is correct
26 Correct 15 ms 64604 KB Output is correct
27 Correct 17 ms 64628 KB Output is correct
28 Correct 14 ms 64340 KB Output is correct
29 Correct 16 ms 64600 KB Output is correct
30 Correct 18 ms 64604 KB Output is correct
31 Correct 17 ms 64628 KB Output is correct
32 Correct 17 ms 64600 KB Output is correct
33 Correct 17 ms 64604 KB Output is correct
34 Correct 16 ms 64604 KB Output is correct
35 Correct 16 ms 64600 KB Output is correct
36 Correct 16 ms 64600 KB Output is correct
37 Correct 16 ms 64600 KB Output is correct
38 Correct 124 ms 75660 KB Output is correct
39 Runtime error 278 ms 326396 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 64348 KB Output is correct
2 Correct 13 ms 64348 KB Output is correct
3 Correct 13 ms 64416 KB Output is correct
4 Correct 14 ms 64432 KB Output is correct
5 Correct 26 ms 64344 KB Output is correct
6 Correct 15 ms 64604 KB Output is correct
7 Correct 16 ms 64692 KB Output is correct
8 Correct 14 ms 64348 KB Output is correct
9 Correct 13 ms 64348 KB Output is correct
10 Correct 14 ms 64348 KB Output is correct
11 Correct 15 ms 64456 KB Output is correct
12 Correct 16 ms 64604 KB Output is correct
13 Correct 51 ms 64644 KB Output is correct
14 Correct 80 ms 64344 KB Output is correct
15 Correct 62 ms 64592 KB Output is correct
16 Runtime error 278 ms 314708 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64336 KB Output is correct
2 Correct 13 ms 64348 KB Output is correct
3 Correct 13 ms 64436 KB Output is correct
4 Correct 39 ms 64684 KB Output is correct
5 Correct 65 ms 65300 KB Output is correct
6 Correct 17 ms 64600 KB Output is correct
7 Correct 16 ms 64756 KB Output is correct
8 Correct 18 ms 64604 KB Output is correct
9 Correct 108 ms 76628 KB Output is correct
10 Runtime error 290 ms 328068 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -