oj.uz

Submission #941617

# Submission time Handle Problem Language Result Execution time Memory
941617 2024-03-09T08:00:24 Z alextodoran Jail (JOI22_jail) C++17
72 / 100
 5000 ms 978100 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;

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

vector <int> out[M_MAX + 2];
int deg[M_MAX + 2];

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

void on_path (int i, int u) {
    if (start_id[u] != 0 && start_id[u] != i) {
        add_edge(start_id[u], i);
    }
    if (finish_id[u] != 0 && finish_id[u] != i) {
        add_edge(i, finish_id[u]);
    }
}

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 <= M; 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;
        }
        for (int i = 1; i <= M; i++) {
            int u = start[i], v = finish[i];
            while (u != v) {
                if (depth[u] > depth[v]) {
                    on_path(i, u);
                    u = parent[u];
                } else {
                    on_path(i, v);
                    v = parent[v];
                }
            }
            on_path(i, u);
        }
        queue <int> q;
        for (int u = 1; u <= M; 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 <= M; 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 3 ms 9052 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9204 KB Output is correct
4 Correct 7 ms 9308 KB Output is correct
5 Correct 14 ms 9964 KB Output is correct
6 Correct 2 ms 9264 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 3 ms 9308 KB Output is correct
9 Correct 77 ms 12884 KB Output is correct
10 Correct 272 ms 23124 KB Output is correct
11 Correct 5 ms 9308 KB Output is correct
12 Correct 26 ms 10332 KB Output is correct
13 Correct 106 ms 52292 KB Output is correct
14 Correct 121 ms 66264 KB Output is correct
15 Execution timed out 5056 ms 978100 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 3 ms 9224 KB Output is correct
4 Correct 3 ms 9220 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 2 ms 9052 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 2 ms 9048 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 3 ms 9224 KB Output is correct
4 Correct 3 ms 9220 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 2 ms 9052 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 2 ms 9048 KB Output is correct
14 Correct 2 ms 9048 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 3 ms 9052 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 3 ms 9052 KB Output is correct
19 Correct 2 ms 9052 KB Output is correct
20 Correct 2 ms 9216 KB Output is correct
21 Correct 3 ms 9052 KB Output is correct
22 Correct 2 ms 9048 KB Output is correct
23 Correct 2 ms 9052 KB Output is correct
24 Correct 2 ms 9052 KB Output is correct
25 Correct 3 ms 9220 KB Output is correct
26 Correct 2 ms 9052 KB Output is correct
27 Correct 2 ms 9052 KB Output is correct
28 Correct 2 ms 9052 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 3 ms 9224 KB Output is correct
4 Correct 3 ms 9220 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 2 ms 9052 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 2 ms 9048 KB Output is correct
14 Correct 2 ms 9048 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 3 ms 9052 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 3 ms 9052 KB Output is correct
19 Correct 2 ms 9052 KB Output is correct
20 Correct 2 ms 9216 KB Output is correct
21 Correct 3 ms 9052 KB Output is correct
22 Correct 2 ms 9048 KB Output is correct
23 Correct 2 ms 9052 KB Output is correct
24 Correct 2 ms 9052 KB Output is correct
25 Correct 3 ms 9220 KB Output is correct
26 Correct 2 ms 9052 KB Output is correct
27 Correct 2 ms 9052 KB Output is correct
28 Correct 2 ms 9052 KB Output is correct
29 Correct 3 ms 9308 KB Output is correct
30 Correct 3 ms 9052 KB Output is correct
31 Correct 3 ms 9052 KB Output is correct
32 Correct 3 ms 9052 KB Output is correct
33 Correct 2 ms 9052 KB Output is correct
34 Correct 3 ms 9052 KB Output is correct
35 Correct 3 ms 9304 KB Output is correct
36 Correct 2 ms 9264 KB Output is correct
37 Correct 2 ms 9052 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 3 ms 9224 KB Output is correct
4 Correct 3 ms 9220 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 2 ms 9052 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 2 ms 9048 KB Output is correct
14 Correct 2 ms 9048 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 3 ms 9052 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 3 ms 9052 KB Output is correct
19 Correct 2 ms 9052 KB Output is correct
20 Correct 2 ms 9216 KB Output is correct
21 Correct 3 ms 9052 KB Output is correct
22 Correct 2 ms 9048 KB Output is correct
23 Correct 2 ms 9052 KB Output is correct
24 Correct 2 ms 9052 KB Output is correct
25 Correct 3 ms 9220 KB Output is correct
26 Correct 2 ms 9052 KB Output is correct
27 Correct 2 ms 9052 KB Output is correct
28 Correct 2 ms 9052 KB Output is correct
29 Correct 3 ms 9308 KB Output is correct
30 Correct 3 ms 9052 KB Output is correct
31 Correct 3 ms 9052 KB Output is correct
32 Correct 3 ms 9052 KB Output is correct
33 Correct 2 ms 9052 KB Output is correct
34 Correct 3 ms 9052 KB Output is correct
35 Correct 3 ms 9304 KB Output is correct
36 Correct 2 ms 9264 KB Output is correct
37 Correct 2 ms 9052 KB Output is correct
38 Correct 75 ms 12884 KB Output is correct
39 Correct 278 ms 23208 KB Output is correct
40 Correct 40 ms 11732 KB Output is correct
41 Correct 20 ms 10588 KB Output is correct
42 Correct 34 ms 11964 KB Output is correct
43 Correct 17 ms 10588 KB Output is correct
44 Correct 6 ms 9564 KB Output is correct
45 Correct 29 ms 14420 KB Output is correct
46 Correct 29 ms 14428 KB Output is correct
47 Correct 68 ms 18020 KB Output is correct
48 Correct 68 ms 17996 KB Output is correct
49 Correct 32 ms 14336 KB Output is correct
50 Correct 38 ms 14416 KB Output is correct
51 Correct 35 ms 15412 KB Output is correct
52 Correct 37 ms 15444 KB Output is correct
53 Correct 7 ms 9728 KB Output is correct
54 Correct 33 ms 14160 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9208 KB Output is correct
2 Correct 2 ms 9048 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 5 ms 9308 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 2 ms 9048 KB Output is correct
10 Correct 3 ms 9304 KB Output is correct
11 Correct 2 ms 9048 KB Output is correct
12 Correct 3 ms 9052 KB Output is correct
13 Correct 13 ms 9588 KB Output is correct
14 Correct 20 ms 9828 KB Output is correct
15 Correct 21 ms 9828 KB Output is correct
16 Correct 33 ms 14808 KB Output is correct
17 Correct 72 ms 20696 KB Output is correct
18 Correct 160 ms 39988 KB Output is correct
19 Correct 34 ms 14888 KB Output is correct
20 Correct 38 ms 15008 KB Output is correct
21 Correct 34 ms 14936 KB Output is correct
22 Correct 62 ms 21072 KB Output is correct
23 Correct 58 ms 21540 KB Output is correct
24 Correct 72 ms 21196 KB Output is correct
25 Correct 58 ms 21360 KB Output is correct
26 Correct 57 ms 21276 KB Output is correct
27 Correct 66 ms 20172 KB Output is correct
28 Correct 77 ms 20020 KB Output is correct
29 Correct 56 ms 20168 KB Output is correct
30 Correct 44 ms 17356 KB Output is correct
31 Correct 42 ms 17360 KB Output is correct
32 Correct 50 ms 17208 KB Output is correct
33 Correct 43 ms 17144 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9204 KB Output is correct
4 Correct 7 ms 9308 KB Output is correct
5 Correct 14 ms 9964 KB Output is correct
6 Correct 2 ms 9264 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 3 ms 9308 KB Output is correct
9 Correct 77 ms 12884 KB Output is correct
10 Correct 272 ms 23124 KB Output is correct
11 Correct 5 ms 9308 KB Output is correct
12 Correct 26 ms 10332 KB Output is correct
13 Correct 106 ms 52292 KB Output is correct
14 Correct 121 ms 66264 KB Output is correct
15 Execution timed out 5056 ms 978100 KB Time limit exceeded
16 Halted 0 ms 0 KB -