oj.uz

Submission #1040127

# Submission time Handle Problem Language Result Execution time Memory
1040127 2024-07-31T16:46:13 Z Sharky Jail (JOI22_jail) C++17
77 / 100
 5000 ms 439660 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 120008;
const int LG = 17;

int n, m, sz[N], dep[N], node = 0, pr[N][LG], rt[N], tin[N], pa[N], timer = 0, leaf[N * 3], ls[N * 20], rs[N * 20], st[2], vis[N * 20], cyc = 0, col[N * 20];
vector<int> adj[N], g[N * 20];

void dfs(int u) {
    sz[u] = 1;
    for (int i = 1; i < LG; i++) pr[u][i] = pr[pr[u][i - 1]][i - 1];
    for (auto& v : adj[u]) {
        if (v == pr[u][0]) continue;
        pr[v][0] = u;
        dep[v] = dep[u] + 1;
        pa[v] = u;
        dfs(v);
        if (sz[v] > sz[adj[u][0]]) swap(v, adj[u][0]);
        sz[u] += sz[v];
    }
}

void dfs_hld(int u) {
    tin[u] = ++timer;
    for (int v : adj[u]) {
        if (v == pr[u][0]) continue;
        rt[v] = (v == adj[u][0] ? rt[u] : v);
        dfs_hld(v);
    }
}

int jump(int s, int di) {
    for (int i = LG - 1; i >= 0; i--) 
        if (di & (1 << i)) s = pr[s][i];
    return s;
}

int lca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    v = jump(v, dep[v] - dep[u]);
    if (u == v) return u;
    for (int i = LG - 1; i >= 0; i--) {
        int ut = pr[u][i], vt = pr[v][i];
        if (ut != vt) u = ut, v = vt;
    }
    return pr[u][0];
}

void build(int l, int r, int id, bool up) {
    if (l == r) {
        leaf[l] = id;
        return;
    }
    int mid = (l + r) / 2;
    if (l != mid || !up) {
        ls[id] = ++node;
        build(l, mid, ls[id], up);
    } else ls[id] = leaf[l];
    if (mid + 1 != r || !up) {
        rs[id] = ++node;
        build(mid + 1, r, rs[id], up);
    } else rs[id] = leaf[r];
    if (!up) {
        g[id].push_back(ls[id]);
        g[id].push_back(rs[id]);
    } else {
        g[ls[id]].push_back(id);
        g[rs[id]].push_back(id);
    }
}

void update(int ql, int qr, int v, int l, int r, int id, bool up) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        if (!up) {
            // cout << "edge: " << v << "-->" << '[' << l << ", " << r << ']' << "\n";
            g[leaf[v]].push_back(id);
        } else {
            // cout << "edge: " << '[' << l << ", " << r << ']' << " --> " << v << "\n";
            g[id].push_back(leaf[v]);
        }
        return;
    }
    int mid = (l + r) / 2;
    update(ql, qr, v, l, mid, ls[id], up);
    update(ql, qr, v, mid + 1, r, rs[id], up);
}

void pti(int x, int l, int r) {
    update(l, r, x, 1, 2 * n + m, st[0], 0);
}

void itp(int x, int l, int r) {
    update(l, r, x, 1, 2 * n + m, st[1], 1);
}

void path(int x, int u, int v, bool b) {
    // cout << x << " " << u << " " << v << " " << b << "\n";
    for (; rt[u] != rt[v]; v = pa[rt[v]]) {
        if (dep[rt[u]] > dep[rt[v]]) swap(u, v);
        if (!b) pti(x + 2 * n, tin[rt[v]] + n, tin[v] + n);
        else itp(x + 2 * n, tin[rt[v]], tin[v]);
    }
    if (dep[u] > dep[v]) swap(u, v);
    if (!b) pti(x + 2 * n, tin[u] + n, tin[v] + n);
    else itp(x + 2 * n, tin[u], tin[v]);
}

bool DFS(int u) {
    col[u] = 1;
    for (int v : g[u]) {
        if (!col[v]) {
            if (DFS(v)) {
                cyc = 1;
                return true;
            }
        } else if (col[v] == 1) {
            cyc = 1;
            return true;
        }
    }
    col[u] = 2;
    return false;
}

void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cin >> m;
    rt[1] = pr[1][0] = 1;
    dfs(1); dfs_hld(1);
    st[0] = ++node;
    build(1, 2 * n + m, node, 0);
    st[1] = ++node;
    build(1, 2 * n + m, node, 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        int x = lca(u, v);
        g[leaf[n * 2 + i]].push_back(leaf[tin[u]]);
        g[leaf[tin[v] + n]].push_back(leaf[n * 2 + i]);
        // cout << "edge: " << n * 2 + i << " --> " << tin[u] << '\n';
        // cout << "edge: " << tin[v] + n << " --> " << n * 2 + i << '\n';
        int d = max(dep[u], dep[v]) - dep[x] - 1;
        if (u != x) {
            path(i, pa[u], v, 1);
        } else {
            path(i, jump(v, d), v, 1);
        }
        if (v != x) {
            path(i, u, pa[v], 0);
        } else {
            path(i, u, jump(u, d), 0);
        }
    }
    // for (int i = 1; i <= node; i++) for (int j : g[i]) cout << i << " --> " << j << '\n';
    for (int i = 1; i <= node; i++) if (!col[i] && DFS(i)) break;
    cout << (cyc ? "No" : "Yes") << '\n';
    for (int i = 1; i <= n; i++) {
        sz[i] = dep[i] = rt[i] = tin[i] = pa[i] = 0;
        adj[i].clear();
        for (int j = 0; j < LG; j++) pr[i][j] = 0;
    }
    for (int i = 1; i <= n * 3; i++) leaf[i] = 0;
    for (int i = 1; i <= node; i++) {
        g[i].clear();
        ls[i] = rs[i] = col[i] = vis[i] = 0;
    }
    timer = cyc = node = st[0] = st[1] = 0;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int q;
    cin >> q;
    while (q--) solve();   
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 68184 KB Output is correct
2 Correct 9 ms 68188 KB Output is correct
3 Correct 9 ms 70236 KB Output is correct
4 Correct 18 ms 60252 KB Output is correct
5 Correct 28 ms 60256 KB Output is correct
6 Correct 10 ms 60252 KB Output is correct
7 Correct 11 ms 60252 KB Output is correct
8 Correct 11 ms 60256 KB Output is correct
9 Correct 38 ms 63120 KB Output is correct
10 Correct 91 ms 118356 KB Output is correct
11 Correct 14 ms 59992 KB Output is correct
12 Correct 41 ms 60292 KB Output is correct
13 Correct 150 ms 128972 KB Output is correct
14 Correct 138 ms 129152 KB Output is correct
15 Correct 236 ms 134016 KB Output is correct
16 Correct 449 ms 156240 KB Output is correct
17 Correct 187 ms 139344 KB Output is correct
18 Correct 156 ms 135168 KB Output is correct
19 Correct 190 ms 138396 KB Output is correct
20 Correct 179 ms 138448 KB Output is correct
21 Correct 182 ms 139020 KB Output is correct
22 Correct 109 ms 126656 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 59992 KB Output is correct
2 Correct 9 ms 59996 KB Output is correct
3 Correct 10 ms 60252 KB Output is correct
4 Correct 9 ms 60252 KB Output is correct
5 Correct 10 ms 60096 KB Output is correct
6 Correct 10 ms 60248 KB Output is correct
7 Correct 10 ms 60156 KB Output is correct
8 Correct 11 ms 60252 KB Output is correct
9 Correct 9 ms 60504 KB Output is correct
10 Correct 11 ms 60248 KB Output is correct
11 Correct 10 ms 60252 KB Output is correct
12 Correct 10 ms 60252 KB Output is correct
13 Correct 10 ms 60072 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 59992 KB Output is correct
2 Correct 9 ms 59996 KB Output is correct
3 Correct 10 ms 60252 KB Output is correct
4 Correct 9 ms 60252 KB Output is correct
5 Correct 10 ms 60096 KB Output is correct
6 Correct 10 ms 60248 KB Output is correct
7 Correct 10 ms 60156 KB Output is correct
8 Correct 11 ms 60252 KB Output is correct
9 Correct 9 ms 60504 KB Output is correct
10 Correct 11 ms 60248 KB Output is correct
11 Correct 10 ms 60252 KB Output is correct
12 Correct 10 ms 60252 KB Output is correct
13 Correct 10 ms 60072 KB Output is correct
14 Correct 10 ms 59992 KB Output is correct
15 Correct 10 ms 59996 KB Output is correct
16 Correct 10 ms 60316 KB Output is correct
17 Correct 10 ms 60252 KB Output is correct
18 Correct 10 ms 60252 KB Output is correct
19 Correct 9 ms 59996 KB Output is correct
20 Correct 10 ms 60320 KB Output is correct
21 Correct 9 ms 60252 KB Output is correct
22 Correct 10 ms 60320 KB Output is correct
23 Correct 9 ms 59996 KB Output is correct
24 Correct 10 ms 60252 KB Output is correct
25 Correct 10 ms 60248 KB Output is correct
26 Correct 9 ms 60252 KB Output is correct
27 Correct 10 ms 60252 KB Output is correct
28 Correct 9 ms 59996 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 59992 KB Output is correct
2 Correct 9 ms 59996 KB Output is correct
3 Correct 10 ms 60252 KB Output is correct
4 Correct 9 ms 60252 KB Output is correct
5 Correct 10 ms 60096 KB Output is correct
6 Correct 10 ms 60248 KB Output is correct
7 Correct 10 ms 60156 KB Output is correct
8 Correct 11 ms 60252 KB Output is correct
9 Correct 9 ms 60504 KB Output is correct
10 Correct 11 ms 60248 KB Output is correct
11 Correct 10 ms 60252 KB Output is correct
12 Correct 10 ms 60252 KB Output is correct
13 Correct 10 ms 60072 KB Output is correct
14 Correct 10 ms 59992 KB Output is correct
15 Correct 10 ms 59996 KB Output is correct
16 Correct 10 ms 60316 KB Output is correct
17 Correct 10 ms 60252 KB Output is correct
18 Correct 10 ms 60252 KB Output is correct
19 Correct 9 ms 59996 KB Output is correct
20 Correct 10 ms 60320 KB Output is correct
21 Correct 9 ms 60252 KB Output is correct
22 Correct 10 ms 60320 KB Output is correct
23 Correct 9 ms 59996 KB Output is correct
24 Correct 10 ms 60252 KB Output is correct
25 Correct 10 ms 60248 KB Output is correct
26 Correct 9 ms 60252 KB Output is correct
27 Correct 10 ms 60252 KB Output is correct
28 Correct 9 ms 59996 KB Output is correct
29 Correct 10 ms 60252 KB Output is correct
30 Correct 11 ms 60288 KB Output is correct
31 Correct 12 ms 60248 KB Output is correct
32 Correct 13 ms 60252 KB Output is correct
33 Correct 11 ms 60252 KB Output is correct
34 Correct 12 ms 60304 KB Output is correct
35 Correct 14 ms 60252 KB Output is correct
36 Correct 10 ms 60304 KB Output is correct
37 Correct 10 ms 60328 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 59992 KB Output is correct
2 Correct 9 ms 59996 KB Output is correct
3 Correct 10 ms 60252 KB Output is correct
4 Correct 9 ms 60252 KB Output is correct
5 Correct 10 ms 60096 KB Output is correct
6 Correct 10 ms 60248 KB Output is correct
7 Correct 10 ms 60156 KB Output is correct
8 Correct 11 ms 60252 KB Output is correct
9 Correct 9 ms 60504 KB Output is correct
10 Correct 11 ms 60248 KB Output is correct
11 Correct 10 ms 60252 KB Output is correct
12 Correct 10 ms 60252 KB Output is correct
13 Correct 10 ms 60072 KB Output is correct
14 Correct 10 ms 59992 KB Output is correct
15 Correct 10 ms 59996 KB Output is correct
16 Correct 10 ms 60316 KB Output is correct
17 Correct 10 ms 60252 KB Output is correct
18 Correct 10 ms 60252 KB Output is correct
19 Correct 9 ms 59996 KB Output is correct
20 Correct 10 ms 60320 KB Output is correct
21 Correct 9 ms 60252 KB Output is correct
22 Correct 10 ms 60320 KB Output is correct
23 Correct 9 ms 59996 KB Output is correct
24 Correct 10 ms 60252 KB Output is correct
25 Correct 10 ms 60248 KB Output is correct
26 Correct 9 ms 60252 KB Output is correct
27 Correct 10 ms 60252 KB Output is correct
28 Correct 9 ms 59996 KB Output is correct
29 Correct 10 ms 60252 KB Output is correct
30 Correct 11 ms 60288 KB Output is correct
31 Correct 12 ms 60248 KB Output is correct
32 Correct 13 ms 60252 KB Output is correct
33 Correct 11 ms 60252 KB Output is correct
34 Correct 12 ms 60304 KB Output is correct
35 Correct 14 ms 60252 KB Output is correct
36 Correct 10 ms 60304 KB Output is correct
37 Correct 10 ms 60328 KB Output is correct
38 Correct 38 ms 63068 KB Output is correct
39 Correct 91 ms 118352 KB Output is correct
40 Correct 250 ms 69968 KB Output is correct
41 Correct 71 ms 63060 KB Output is correct
42 Correct 46 ms 63056 KB Output is correct
43 Correct 34 ms 62556 KB Output is correct
44 Correct 30 ms 60760 KB Output is correct
45 Correct 103 ms 109392 KB Output is correct
46 Correct 114 ms 109400 KB Output is correct
47 Correct 702 ms 152656 KB Output is correct
48 Correct 696 ms 153428 KB Output is correct
49 Correct 151 ms 112208 KB Output is correct
50 Correct 163 ms 112124 KB Output is correct
51 Correct 84 ms 110520 KB Output is correct
52 Correct 83 ms 110416 KB Output is correct
53 Correct 27 ms 63532 KB Output is correct
54 Correct 111 ms 109104 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 59996 KB Output is correct
2 Correct 9 ms 59996 KB Output is correct
3 Correct 8 ms 60052 KB Output is correct
4 Correct 8 ms 59996 KB Output is correct
5 Correct 14 ms 60220 KB Output is correct
6 Correct 10 ms 60252 KB Output is correct
7 Correct 9 ms 60060 KB Output is correct
8 Correct 8 ms 59996 KB Output is correct
9 Correct 9 ms 59996 KB Output is correct
10 Correct 9 ms 60252 KB Output is correct
11 Correct 8 ms 60048 KB Output is correct
12 Correct 13 ms 60252 KB Output is correct
13 Correct 42 ms 60252 KB Output is correct
14 Correct 58 ms 60268 KB Output is correct
15 Correct 49 ms 60272 KB Output is correct
16 Correct 157 ms 112036 KB Output is correct
17 Correct 469 ms 127180 KB Output is correct
18 Correct 897 ms 145728 KB Output is correct
19 Correct 278 ms 115024 KB Output is correct
20 Correct 230 ms 115284 KB Output is correct
21 Correct 291 ms 115452 KB Output is correct
22 Correct 454 ms 126544 KB Output is correct
23 Correct 376 ms 126672 KB Output is correct
24 Correct 417 ms 125904 KB Output is correct
25 Correct 395 ms 126284 KB Output is correct
26 Correct 428 ms 126540 KB Output is correct
27 Correct 398 ms 129804 KB Output is correct
28 Correct 365 ms 138160 KB Output is correct
29 Correct 323 ms 129240 KB Output is correct
30 Correct 297 ms 123440 KB Output is correct
31 Correct 299 ms 126160 KB Output is correct
32 Correct 292 ms 123496 KB Output is correct
33 Correct 278 ms 126412 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 68184 KB Output is correct
2 Correct 9 ms 68188 KB Output is correct
3 Correct 9 ms 70236 KB Output is correct
4 Correct 18 ms 60252 KB Output is correct
5 Correct 28 ms 60256 KB Output is correct
6 Correct 10 ms 60252 KB Output is correct
7 Correct 11 ms 60252 KB Output is correct
8 Correct 11 ms 60256 KB Output is correct
9 Correct 38 ms 63120 KB Output is correct
10 Correct 91 ms 118356 KB Output is correct
11 Correct 14 ms 59992 KB Output is correct
12 Correct 41 ms 60292 KB Output is correct
13 Correct 150 ms 128972 KB Output is correct
14 Correct 138 ms 129152 KB Output is correct
15 Correct 236 ms 134016 KB Output is correct
16 Correct 449 ms 156240 KB Output is correct
17 Correct 187 ms 139344 KB Output is correct
18 Correct 156 ms 135168 KB Output is correct
19 Correct 190 ms 138396 KB Output is correct
20 Correct 179 ms 138448 KB Output is correct
21 Correct 182 ms 139020 KB Output is correct
22 Correct 109 ms 126656 KB Output is correct
23 Correct 9 ms 59992 KB Output is correct
24 Correct 9 ms 59996 KB Output is correct
25 Correct 10 ms 60252 KB Output is correct
26 Correct 9 ms 60252 KB Output is correct
27 Correct 10 ms 60096 KB Output is correct
28 Correct 10 ms 60248 KB Output is correct
29 Correct 10 ms 60156 KB Output is correct
30 Correct 11 ms 60252 KB Output is correct
31 Correct 9 ms 60504 KB Output is correct
32 Correct 11 ms 60248 KB Output is correct
33 Correct 10 ms 60252 KB Output is correct
34 Correct 10 ms 60252 KB Output is correct
35 Correct 10 ms 60072 KB Output is correct
36 Correct 10 ms 59992 KB Output is correct
37 Correct 10 ms 59996 KB Output is correct
38 Correct 10 ms 60316 KB Output is correct
39 Correct 10 ms 60252 KB Output is correct
40 Correct 10 ms 60252 KB Output is correct
41 Correct 9 ms 59996 KB Output is correct
42 Correct 10 ms 60320 KB Output is correct
43 Correct 9 ms 60252 KB Output is correct
44 Correct 10 ms 60320 KB Output is correct
45 Correct 9 ms 59996 KB Output is correct
46 Correct 10 ms 60252 KB Output is correct
47 Correct 10 ms 60248 KB Output is correct
48 Correct 9 ms 60252 KB Output is correct
49 Correct 10 ms 60252 KB Output is correct
50 Correct 9 ms 59996 KB Output is correct
51 Correct 10 ms 60252 KB Output is correct
52 Correct 11 ms 60288 KB Output is correct
53 Correct 12 ms 60248 KB Output is correct
54 Correct 13 ms 60252 KB Output is correct
55 Correct 11 ms 60252 KB Output is correct
56 Correct 12 ms 60304 KB Output is correct
57 Correct 14 ms 60252 KB Output is correct
58 Correct 10 ms 60304 KB Output is correct
59 Correct 10 ms 60328 KB Output is correct
60 Correct 38 ms 63068 KB Output is correct
61 Correct 91 ms 118352 KB Output is correct
62 Correct 250 ms 69968 KB Output is correct
63 Correct 71 ms 63060 KB Output is correct
64 Correct 46 ms 63056 KB Output is correct
65 Correct 34 ms 62556 KB Output is correct
66 Correct 30 ms 60760 KB Output is correct
67 Correct 103 ms 109392 KB Output is correct
68 Correct 114 ms 109400 KB Output is correct
69 Correct 702 ms 152656 KB Output is correct
70 Correct 696 ms 153428 KB Output is correct
71 Correct 151 ms 112208 KB Output is correct
72 Correct 163 ms 112124 KB Output is correct
73 Correct 84 ms 110520 KB Output is correct
74 Correct 83 ms 110416 KB Output is correct
75 Correct 27 ms 63532 KB Output is correct
76 Correct 111 ms 109104 KB Output is correct
77 Correct 10 ms 59996 KB Output is correct
78 Correct 9 ms 59996 KB Output is correct
79 Correct 8 ms 60052 KB Output is correct
80 Correct 8 ms 59996 KB Output is correct
81 Correct 14 ms 60220 KB Output is correct
82 Correct 10 ms 60252 KB Output is correct
83 Correct 9 ms 60060 KB Output is correct
84 Correct 8 ms 59996 KB Output is correct
85 Correct 9 ms 59996 KB Output is correct
86 Correct 9 ms 60252 KB Output is correct
87 Correct 8 ms 60048 KB Output is correct
88 Correct 13 ms 60252 KB Output is correct
89 Correct 42 ms 60252 KB Output is correct
90 Correct 58 ms 60268 KB Output is correct
91 Correct 49 ms 60272 KB Output is correct
92 Correct 157 ms 112036 KB Output is correct
93 Correct 469 ms 127180 KB Output is correct
94 Correct 897 ms 145728 KB Output is correct
95 Correct 278 ms 115024 KB Output is correct
96 Correct 230 ms 115284 KB Output is correct
97 Correct 291 ms 115452 KB Output is correct
98 Correct 454 ms 126544 KB Output is correct
99 Correct 376 ms 126672 KB Output is correct
100 Correct 417 ms 125904 KB Output is correct
101 Correct 395 ms 126284 KB Output is correct
102 Correct 428 ms 126540 KB Output is correct
103 Correct 398 ms 129804 KB Output is correct
104 Correct 365 ms 138160 KB Output is correct
105 Correct 323 ms 129240 KB Output is correct
106 Correct 297 ms 123440 KB Output is correct
107 Correct 299 ms 126160 KB Output is correct
108 Correct 292 ms 123496 KB Output is correct
109 Correct 278 ms 126412 KB Output is correct
110 Correct 55 ms 60248 KB Output is correct
111 Correct 31 ms 60248 KB Output is correct
112 Execution timed out 5047 ms 439660 KB Time limit exceeded
113 Halted 0 ms 0 KB -