oj.uz

Submission #710535

# Submission time Handle Problem Language Result Execution time Memory
710535 2023-03-15T10:28:23 Z becaido Jail (JOI22_jail) C++17
100 / 100
 1541 ms 394644 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

// s[i] lies on path(s[j], t[j]), build an edge(i -> j)
// t[i] lies on path(s[j], t[j]), build an edge(j -> i)

const int SIZE = 3.6e5 + 5;
const int H = __lg(SIZE) + 1;

int n, m;
int s[SIZE], t[SIZE];
vector<int> adj[SIZE];

int sz;
queue<int> q;
vector<int> edge[SIZE * H];
int h[SIZE], to[SIZE][H + 1];
int deg[SIZE * H], in[SIZE][H + 1], out[SIZE][H + 1]; // in : large to small, out small to large

int jump(int pos, int k) {
    int cnt = 0;
    while (k) {
        if (k & 1) pos = to[pos][cnt];
        cnt++;
        k >>= 1;
    }
    return pos;
}

int lca(int a, int b) {
    if (h[a] < h[b]) swap(a, b);
    a = jump(a, h[a] - h[b]);
    if (a == b) return a;
    for (int i = H; i >= 0; i--) if (to[a][i] != to[b][i]) {
        a = to[a][i];
        b = to[b][i];
    }
    return to[a][0];
}

int walk(int a, int b) {
    int c = lca(a, b);
    if (h[a] > h[c]) return to[a][0];
    return jump(b, h[b] - h[a] - 1);
}

int newnode() {
    sz++;
    edge[sz].clear();
    deg[sz] = 0;
    return sz;
}

void add(int pos, int k, int ty, int x) {
    int cnt = 0;
    while (k) {
        if (k & 1) {
            if (ty == 0) edge[out[pos][cnt]].pb(x);
            if (ty == 1) edge[x].pb(in[pos][cnt]);
            pos = to[pos][cnt];
        }
        cnt++;
        k >>= 1;
    }
}

void add_edge(int x, int a, int b, int ty) {
    int c = lca(a, b);
    add(a, h[a] - h[c] + 1, ty, x);
    add(b, h[b] - h[c] + 1, ty, x);
}

void solve() {
    cin >> n;
    FOR (i, 1, n) {
        adj[i].clear();
        edge[i].clear();
        deg[i] = 0;
    }
    FOR (i, 2, n) {
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    cin >> m;
    FOR (i, 1, m) cin >> s[i] >> t[i];

    auto dfs = [&](auto dfs, int pos)->void {
        for (int np : adj[pos]) if (np != to[pos][0]) {
            h[np] = h[pos] + 1;
            to[np][0] = pos;
            dfs(dfs, np);
        }
    };
    h[1] = 1;
    dfs(dfs, 1);
    sz = m;
    FOR (i, 1, n) {
        in[i][0] = newnode();
        out[i][0] = newnode();
    }
    FOR (j, 1, H) FOR (i, 1, n) {
        to[i][j] = to[to[i][j - 1]][j - 1];
        in[i][j] = newnode();
        out[i][j] = newnode();
        edge[in[i][j]].pb(in[i][j - 1]);
        edge[out[i][j - 1]].pb(out[i][j]);
        if (to[i][j - 1]) {
            edge[in[i][j]].pb(in[to[i][j - 1]][j - 1]);
            edge[out[to[i][j - 1]][j - 1]].pb(out[i][j]);
        }
    }
    FOR (i, 1, m) {
        edge[i].pb(out[s[i]][0]);
        edge[in[t[i]][0]].pb(i);
    }

    FOR (i, 1, m) {
        add_edge(i, walk(s[i], t[i]), t[i], 0);
        add_edge(i, s[i], walk(t[i], s[i]), 1);
    }
    FOR (i, 1, sz) for (int j : edge[i]) deg[j]++;
    FOR (i, 1, sz) if (!deg[i]) q.push(i);
    int cnt = 0;
    while (q.size()) {
        int pos = q.front();
        q.pop();
        cnt++;
        for (int np : edge[pos]) if (--deg[np] == 0) q.push(np);
    }
    cout << (cnt == sz ? "Yes" : "No") << '\n';
}

int main() {
    Waimai;
    int tt;
    cin >> tt;
    while (tt--) solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 169400 KB Output is correct
2 Correct 99 ms 169416 KB Output is correct
3 Correct 85 ms 169400 KB Output is correct
4 Correct 158 ms 169816 KB Output is correct
5 Correct 232 ms 169792 KB Output is correct
6 Correct 103 ms 169876 KB Output is correct
7 Correct 105 ms 169884 KB Output is correct
8 Correct 96 ms 169908 KB Output is correct
9 Correct 365 ms 179856 KB Output is correct
10 Correct 828 ms 369412 KB Output is correct
11 Correct 132 ms 169588 KB Output is correct
12 Correct 248 ms 170532 KB Output is correct
13 Correct 1016 ms 377032 KB Output is correct
14 Correct 861 ms 376940 KB Output is correct
15 Correct 1097 ms 378552 KB Output is correct
16 Correct 1520 ms 390328 KB Output is correct
17 Correct 821 ms 380236 KB Output is correct
18 Correct 865 ms 379840 KB Output is correct
19 Correct 803 ms 378512 KB Output is correct
20 Correct 696 ms 378432 KB Output is correct
21 Correct 753 ms 380196 KB Output is correct
22 Correct 660 ms 375700 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 169476 KB Output is correct
2 Correct 97 ms 169432 KB Output is correct
3 Correct 107 ms 169848 KB Output is correct
4 Correct 95 ms 169796 KB Output is correct
5 Correct 93 ms 169776 KB Output is correct
6 Correct 98 ms 169876 KB Output is correct
7 Correct 109 ms 169860 KB Output is correct
8 Correct 103 ms 169852 KB Output is correct
9 Correct 94 ms 169804 KB Output is correct
10 Correct 97 ms 169868 KB Output is correct
11 Correct 105 ms 169856 KB Output is correct
12 Correct 102 ms 169796 KB Output is correct
13 Correct 94 ms 169840 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 169476 KB Output is correct
2 Correct 97 ms 169432 KB Output is correct
3 Correct 107 ms 169848 KB Output is correct
4 Correct 95 ms 169796 KB Output is correct
5 Correct 93 ms 169776 KB Output is correct
6 Correct 98 ms 169876 KB Output is correct
7 Correct 109 ms 169860 KB Output is correct
8 Correct 103 ms 169852 KB Output is correct
9 Correct 94 ms 169804 KB Output is correct
10 Correct 97 ms 169868 KB Output is correct
11 Correct 105 ms 169856 KB Output is correct
12 Correct 102 ms 169796 KB Output is correct
13 Correct 94 ms 169840 KB Output is correct
14 Correct 88 ms 169324 KB Output is correct
15 Correct 89 ms 169380 KB Output is correct
16 Correct 97 ms 169788 KB Output is correct
17 Correct 96 ms 169860 KB Output is correct
18 Correct 93 ms 169892 KB Output is correct
19 Correct 97 ms 169420 KB Output is correct
20 Correct 99 ms 169752 KB Output is correct
21 Correct 98 ms 169768 KB Output is correct
22 Correct 93 ms 169868 KB Output is correct
23 Correct 86 ms 169528 KB Output is correct
24 Correct 94 ms 169648 KB Output is correct
25 Correct 97 ms 169864 KB Output is correct
26 Correct 92 ms 169956 KB Output is correct
27 Correct 94 ms 169796 KB Output is correct
28 Correct 89 ms 169420 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 169476 KB Output is correct
2 Correct 97 ms 169432 KB Output is correct
3 Correct 107 ms 169848 KB Output is correct
4 Correct 95 ms 169796 KB Output is correct
5 Correct 93 ms 169776 KB Output is correct
6 Correct 98 ms 169876 KB Output is correct
7 Correct 109 ms 169860 KB Output is correct
8 Correct 103 ms 169852 KB Output is correct
9 Correct 94 ms 169804 KB Output is correct
10 Correct 97 ms 169868 KB Output is correct
11 Correct 105 ms 169856 KB Output is correct
12 Correct 102 ms 169796 KB Output is correct
13 Correct 94 ms 169840 KB Output is correct
14 Correct 88 ms 169324 KB Output is correct
15 Correct 89 ms 169380 KB Output is correct
16 Correct 97 ms 169788 KB Output is correct
17 Correct 96 ms 169860 KB Output is correct
18 Correct 93 ms 169892 KB Output is correct
19 Correct 97 ms 169420 KB Output is correct
20 Correct 99 ms 169752 KB Output is correct
21 Correct 98 ms 169768 KB Output is correct
22 Correct 93 ms 169868 KB Output is correct
23 Correct 86 ms 169528 KB Output is correct
24 Correct 94 ms 169648 KB Output is correct
25 Correct 97 ms 169864 KB Output is correct
26 Correct 92 ms 169956 KB Output is correct
27 Correct 94 ms 169796 KB Output is correct
28 Correct 89 ms 169420 KB Output is correct
29 Correct 97 ms 169768 KB Output is correct
30 Correct 93 ms 169892 KB Output is correct
31 Correct 95 ms 169804 KB Output is correct
32 Correct 99 ms 169844 KB Output is correct
33 Correct 106 ms 169884 KB Output is correct
34 Correct 105 ms 169768 KB Output is correct
35 Correct 97 ms 169808 KB Output is correct
36 Correct 91 ms 169740 KB Output is correct
37 Correct 100 ms 169752 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 169476 KB Output is correct
2 Correct 97 ms 169432 KB Output is correct
3 Correct 107 ms 169848 KB Output is correct
4 Correct 95 ms 169796 KB Output is correct
5 Correct 93 ms 169776 KB Output is correct
6 Correct 98 ms 169876 KB Output is correct
7 Correct 109 ms 169860 KB Output is correct
8 Correct 103 ms 169852 KB Output is correct
9 Correct 94 ms 169804 KB Output is correct
10 Correct 97 ms 169868 KB Output is correct
11 Correct 105 ms 169856 KB Output is correct
12 Correct 102 ms 169796 KB Output is correct
13 Correct 94 ms 169840 KB Output is correct
14 Correct 88 ms 169324 KB Output is correct
15 Correct 89 ms 169380 KB Output is correct
16 Correct 97 ms 169788 KB Output is correct
17 Correct 96 ms 169860 KB Output is correct
18 Correct 93 ms 169892 KB Output is correct
19 Correct 97 ms 169420 KB Output is correct
20 Correct 99 ms 169752 KB Output is correct
21 Correct 98 ms 169768 KB Output is correct
22 Correct 93 ms 169868 KB Output is correct
23 Correct 86 ms 169528 KB Output is correct
24 Correct 94 ms 169648 KB Output is correct
25 Correct 97 ms 169864 KB Output is correct
26 Correct 92 ms 169956 KB Output is correct
27 Correct 94 ms 169796 KB Output is correct
28 Correct 89 ms 169420 KB Output is correct
29 Correct 97 ms 169768 KB Output is correct
30 Correct 93 ms 169892 KB Output is correct
31 Correct 95 ms 169804 KB Output is correct
32 Correct 99 ms 169844 KB Output is correct
33 Correct 106 ms 169884 KB Output is correct
34 Correct 105 ms 169768 KB Output is correct
35 Correct 97 ms 169808 KB Output is correct
36 Correct 91 ms 169740 KB Output is correct
37 Correct 100 ms 169752 KB Output is correct
38 Correct 370 ms 179600 KB Output is correct
39 Correct 799 ms 369244 KB Output is correct
40 Correct 393 ms 181968 KB Output is correct
41 Correct 377 ms 180944 KB Output is correct
42 Correct 291 ms 181496 KB Output is correct
43 Correct 415 ms 181964 KB Output is correct
44 Correct 130 ms 171420 KB Output is correct
45 Correct 726 ms 368268 KB Output is correct
46 Correct 755 ms 368208 KB Output is correct
47 Correct 760 ms 368520 KB Output is correct
48 Correct 754 ms 368608 KB Output is correct
49 Correct 760 ms 370772 KB Output is correct
50 Correct 852 ms 370764 KB Output is correct
51 Correct 898 ms 371220 KB Output is correct
52 Correct 860 ms 371192 KB Output is correct
53 Correct 192 ms 183792 KB Output is correct
54 Correct 992 ms 368536 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 169408 KB Output is correct
2 Correct 105 ms 169436 KB Output is correct
3 Correct 94 ms 169444 KB Output is correct
4 Correct 91 ms 169432 KB Output is correct
5 Correct 118 ms 169448 KB Output is correct
6 Correct 105 ms 169808 KB Output is correct
7 Correct 88 ms 169844 KB Output is correct
8 Correct 88 ms 169428 KB Output is correct
9 Correct 89 ms 169424 KB Output is correct
10 Correct 88 ms 169600 KB Output is correct
11 Correct 91 ms 169532 KB Output is correct
12 Correct 91 ms 169816 KB Output is correct
13 Correct 176 ms 169660 KB Output is correct
14 Correct 240 ms 169660 KB Output is correct
15 Correct 231 ms 169724 KB Output is correct
16 Correct 823 ms 367532 KB Output is correct
17 Correct 817 ms 375580 KB Output is correct
18 Correct 995 ms 384364 KB Output is correct
19 Correct 850 ms 370400 KB Output is correct
20 Correct 843 ms 370328 KB Output is correct
21 Correct 782 ms 370280 KB Output is correct
22 Correct 818 ms 376004 KB Output is correct
23 Correct 719 ms 376336 KB Output is correct
24 Correct 1022 ms 375756 KB Output is correct
25 Correct 1014 ms 376276 KB Output is correct
26 Correct 956 ms 375984 KB Output is correct
27 Correct 785 ms 377584 KB Output is correct
28 Correct 648 ms 377456 KB Output is correct
29 Correct 670 ms 377576 KB Output is correct
30 Correct 984 ms 371808 KB Output is correct
31 Correct 717 ms 371808 KB Output is correct
32 Correct 1104 ms 372012 KB Output is correct
33 Correct 668 ms 372056 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 169400 KB Output is correct
2 Correct 99 ms 169416 KB Output is correct
3 Correct 85 ms 169400 KB Output is correct
4 Correct 158 ms 169816 KB Output is correct
5 Correct 232 ms 169792 KB Output is correct
6 Correct 103 ms 169876 KB Output is correct
7 Correct 105 ms 169884 KB Output is correct
8 Correct 96 ms 169908 KB Output is correct
9 Correct 365 ms 179856 KB Output is correct
10 Correct 828 ms 369412 KB Output is correct
11 Correct 132 ms 169588 KB Output is correct
12 Correct 248 ms 170532 KB Output is correct
13 Correct 1016 ms 377032 KB Output is correct
14 Correct 861 ms 376940 KB Output is correct
15 Correct 1097 ms 378552 KB Output is correct
16 Correct 1520 ms 390328 KB Output is correct
17 Correct 821 ms 380236 KB Output is correct
18 Correct 865 ms 379840 KB Output is correct
19 Correct 803 ms 378512 KB Output is correct
20 Correct 696 ms 378432 KB Output is correct
21 Correct 753 ms 380196 KB Output is correct
22 Correct 660 ms 375700 KB Output is correct
23 Correct 89 ms 169476 KB Output is correct
24 Correct 97 ms 169432 KB Output is correct
25 Correct 107 ms 169848 KB Output is correct
26 Correct 95 ms 169796 KB Output is correct
27 Correct 93 ms 169776 KB Output is correct
28 Correct 98 ms 169876 KB Output is correct
29 Correct 109 ms 169860 KB Output is correct
30 Correct 103 ms 169852 KB Output is correct
31 Correct 94 ms 169804 KB Output is correct
32 Correct 97 ms 169868 KB Output is correct
33 Correct 105 ms 169856 KB Output is correct
34 Correct 102 ms 169796 KB Output is correct
35 Correct 94 ms 169840 KB Output is correct
36 Correct 88 ms 169324 KB Output is correct
37 Correct 89 ms 169380 KB Output is correct
38 Correct 97 ms 169788 KB Output is correct
39 Correct 96 ms 169860 KB Output is correct
40 Correct 93 ms 169892 KB Output is correct
41 Correct 97 ms 169420 KB Output is correct
42 Correct 99 ms 169752 KB Output is correct
43 Correct 98 ms 169768 KB Output is correct
44 Correct 93 ms 169868 KB Output is correct
45 Correct 86 ms 169528 KB Output is correct
46 Correct 94 ms 169648 KB Output is correct
47 Correct 97 ms 169864 KB Output is correct
48 Correct 92 ms 169956 KB Output is correct
49 Correct 94 ms 169796 KB Output is correct
50 Correct 89 ms 169420 KB Output is correct
51 Correct 97 ms 169768 KB Output is correct
52 Correct 93 ms 169892 KB Output is correct
53 Correct 95 ms 169804 KB Output is correct
54 Correct 99 ms 169844 KB Output is correct
55 Correct 106 ms 169884 KB Output is correct
56 Correct 105 ms 169768 KB Output is correct
57 Correct 97 ms 169808 KB Output is correct
58 Correct 91 ms 169740 KB Output is correct
59 Correct 100 ms 169752 KB Output is correct
60 Correct 370 ms 179600 KB Output is correct
61 Correct 799 ms 369244 KB Output is correct
62 Correct 393 ms 181968 KB Output is correct
63 Correct 377 ms 180944 KB Output is correct
64 Correct 291 ms 181496 KB Output is correct
65 Correct 415 ms 181964 KB Output is correct
66 Correct 130 ms 171420 KB Output is correct
67 Correct 726 ms 368268 KB Output is correct
68 Correct 755 ms 368208 KB Output is correct
69 Correct 760 ms 368520 KB Output is correct
70 Correct 754 ms 368608 KB Output is correct
71 Correct 760 ms 370772 KB Output is correct
72 Correct 852 ms 370764 KB Output is correct
73 Correct 898 ms 371220 KB Output is correct
74 Correct 860 ms 371192 KB Output is correct
75 Correct 192 ms 183792 KB Output is correct
76 Correct 992 ms 368536 KB Output is correct
77 Correct 89 ms 169408 KB Output is correct
78 Correct 105 ms 169436 KB Output is correct
79 Correct 94 ms 169444 KB Output is correct
80 Correct 91 ms 169432 KB Output is correct
81 Correct 118 ms 169448 KB Output is correct
82 Correct 105 ms 169808 KB Output is correct
83 Correct 88 ms 169844 KB Output is correct
84 Correct 88 ms 169428 KB Output is correct
85 Correct 89 ms 169424 KB Output is correct
86 Correct 88 ms 169600 KB Output is correct
87 Correct 91 ms 169532 KB Output is correct
88 Correct 91 ms 169816 KB Output is correct
89 Correct 176 ms 169660 KB Output is correct
90 Correct 240 ms 169660 KB Output is correct
91 Correct 231 ms 169724 KB Output is correct
92 Correct 823 ms 367532 KB Output is correct
93 Correct 817 ms 375580 KB Output is correct
94 Correct 995 ms 384364 KB Output is correct
95 Correct 850 ms 370400 KB Output is correct
96 Correct 843 ms 370328 KB Output is correct
97 Correct 782 ms 370280 KB Output is correct
98 Correct 818 ms 376004 KB Output is correct
99 Correct 719 ms 376336 KB Output is correct
100 Correct 1022 ms 375756 KB Output is correct
101 Correct 1014 ms 376276 KB Output is correct
102 Correct 956 ms 375984 KB Output is correct
103 Correct 785 ms 377584 KB Output is correct
104 Correct 648 ms 377456 KB Output is correct
105 Correct 670 ms 377576 KB Output is correct
106 Correct 984 ms 371808 KB Output is correct
107 Correct 717 ms 371808 KB Output is correct
108 Correct 1104 ms 372012 KB Output is correct
109 Correct 668 ms 372056 KB Output is correct
110 Correct 247 ms 170936 KB Output is correct
111 Correct 218 ms 170396 KB Output is correct
112 Correct 1154 ms 382920 KB Output is correct
113 Correct 1128 ms 372952 KB Output is correct
114 Correct 853 ms 378280 KB Output is correct
115 Correct 537 ms 366868 KB Output is correct
116 Correct 1258 ms 374180 KB Output is correct
117 Correct 1111 ms 387092 KB Output is correct
118 Correct 1077 ms 368408 KB Output is correct
119 Correct 1068 ms 368412 KB Output is correct
120 Correct 157 ms 186704 KB Output is correct
121 Correct 1453 ms 375976 KB Output is correct
122 Correct 1541 ms 375844 KB Output is correct
123 Correct 1258 ms 373116 KB Output is correct
124 Correct 840 ms 373036 KB Output is correct
125 Correct 1188 ms 373664 KB Output is correct
126 Correct 1469 ms 394644 KB Output is correct
127 Correct 949 ms 384152 KB Output is correct
128 Correct 887 ms 384332 KB Output is correct
129 Correct 1027 ms 384032 KB Output is correct
130 Correct 897 ms 384092 KB Output is correct