oj.uz

Submission #1043523

# Submission time Handle Problem Language Result Execution time Memory
1043523 2024-08-04T10:35:57 Z vladilius Jail (JOI22_jail) C++17
100 / 100
 631 ms 92264 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
const int N = 1.2e5;

vector<int> g[N + 1], G[9 * N];
int s[N + 1], t[N + 1], sz[N + 1], h[N + 1], p[N + 1], d[N + 1], head[N + 1], pos[N + 1], a[N + 1], b[N + 1], k, m, n;

void build1(int v, int tl, int tr){
    if (tl == tr){
        if (a[tl]) G[v + m].pb(a[tl]);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    build1(vv, tl, tm);
    build1(vv + 1, tm + 1, tr);
    G[v + m].pb(vv + m);
    G[v + m].pb(vv + m + 1);
}

void build2(int v, int tl, int tr){
    if (tl == tr){
        if (b[tl]) G[b[tl]].pb(v + k);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    build2(vv, tl, tm);
    build2(vv + 1, tm + 1, tr);
    G[vv + k].pb(v + k);
    G[vv + k + 1].pb(v + k);
}

void add1(int v, int tl, int tr, int& l, int& r, int& u){
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r){
        G[u].pb(v + m);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    add1(vv, tl, tm, l, r, u);
    add1(vv + 1, tm + 1, tr, l, r, u);
}
void add1(int u, int l, int r){
    if (l > r) return;
    add1(1, 1, n, l, r, u);
}

void add2(int v, int tl, int tr, int& l, int& r, int& u){
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r){
        G[v + k].pb(u);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    add2(vv, tl, tm, l, r, u);
    add2(vv + 1, tm + 1, tr, l, r, u);
}
void add2(int u, int l, int r){
    if (l > r) return;
    add2(1, 1, n, l, r, u);
}

bool used[9 * N], seen[9 * N];

bool dfs(int v){
    used[v] = seen[v] = 1;
    for (int i: G[v]){
        if (used[i]){
            if (seen[i]){
                return 0;
            }
            continue;
        }
        if (!dfs(i)) return 0;
    }
    seen[v] = 0;
    return 1;
}

bool check(){
    int nn = 9 * n;
    for (int i = 1; i < nn; i++) used[i] = seen[i] = 0;
    for (int i = 1; i <= nn; i++){
        if (!used[i]){
            if (!dfs(i)){
                return 0;
            }
        }
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int tt; cin>>tt;
    while (tt--){
        cin>>n;
        for (int i = 1; i <= n; i++) g[i].clear();
        for (int i = 1; i < n; i++){
            int x, y; cin>>x>>y;
            g[x].pb(y);
            g[y].pb(x);
        }
        cin>>m;
        for (int i = 1; i <= m; i++){
            cin>>s[i]>>t[i];
        }
        
        for (int i = 1; i <= n; i++) pos[i] = h[i] = a[i] = b[i] = 0;
        
        function<void(int, int)> fill = [&](int v, int pr){
            p[v] = pr;
            sz[v] = 1;
            for (int i: g[v]){
                if (i == pr) continue;
                d[i] = d[v] + 1;
                fill(i, v);
                if (sz[i] > sz[h[v]]){
                    h[v] = i;
                }
                sz[v] += sz[i];
            }
        };
        fill(1, 0);
        
        
        int timer = 0;
        function<void(int, int)> fill_hld = [&](int v, int k){
            head[v] = k;
            pos[v] = ++timer;
            if (!h[v]) return;
            fill_hld(h[v], k);
            for (int i: g[v]){
                if (pos[i]) continue;
                fill_hld(i, i);
            }
        };
        fill_hld(1, 1);
        
        for (int i = 1; i <= m; i++){
            a[pos[s[i]]] = i;
            b[pos[t[i]]] = i;
        }
        
        for (int i = 1; i < 9 * n; i++) G[i].clear();
        k = m + 4 * n;
        build1(1, 1, n);
        build2(1, 1, n);

        for (int i = 1; i <= m; i++){
            int x = s[i], y = t[i];
            while (head[x] != head[y]){
                if (d[head[x]] > d[head[y]]){
                    swap(x, y);
                }
                add1(i, pos[head[y]] + (head[y] == s[i]), pos[y] - (y == s[i]));
                add2(i, pos[head[y]] + (head[y] == t[i]), pos[y] - (y == t[i]));
                y = p[head[y]];
            }
            if (d[x] > d[y]) swap(x, y);
            add1(i, pos[x] + (x == s[i]), pos[y] - (y == s[i]));
            add2(i, pos[x] + (x == t[i]), pos[y] - (y == t[i]));
        }
        
        cout<<((check()) ? "Yes" : "No")<<"\n";
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 5 ms 35164 KB Output is correct
3 Correct 5 ms 35248 KB Output is correct
4 Correct 13 ms 35304 KB Output is correct
5 Correct 28 ms 35304 KB Output is correct
6 Correct 6 ms 35164 KB Output is correct
7 Correct 7 ms 35260 KB Output is correct
8 Correct 7 ms 35320 KB Output is correct
9 Correct 36 ms 37208 KB Output is correct
10 Correct 69 ms 65536 KB Output is correct
11 Correct 11 ms 35272 KB Output is correct
12 Correct 30 ms 35308 KB Output is correct
13 Correct 115 ms 71912 KB Output is correct
14 Correct 86 ms 72048 KB Output is correct
15 Correct 127 ms 76776 KB Output is correct
16 Correct 239 ms 92264 KB Output is correct
17 Correct 140 ms 79956 KB Output is correct
18 Correct 107 ms 72792 KB Output is correct
19 Correct 138 ms 78196 KB Output is correct
20 Correct 107 ms 78280 KB Output is correct
21 Correct 104 ms 78972 KB Output is correct
22 Correct 76 ms 69224 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35160 KB Output is correct
2 Correct 6 ms 35164 KB Output is correct
3 Correct 6 ms 35164 KB Output is correct
4 Correct 6 ms 35160 KB Output is correct
5 Correct 5 ms 35164 KB Output is correct
6 Correct 6 ms 35164 KB Output is correct
7 Correct 6 ms 35228 KB Output is correct
8 Correct 8 ms 35312 KB Output is correct
9 Correct 6 ms 35164 KB Output is correct
10 Correct 6 ms 35164 KB Output is correct
11 Correct 6 ms 35164 KB Output is correct
12 Correct 6 ms 35164 KB Output is correct
13 Correct 9 ms 35164 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35160 KB Output is correct
2 Correct 6 ms 35164 KB Output is correct
3 Correct 6 ms 35164 KB Output is correct
4 Correct 6 ms 35160 KB Output is correct
5 Correct 5 ms 35164 KB Output is correct
6 Correct 6 ms 35164 KB Output is correct
7 Correct 6 ms 35228 KB Output is correct
8 Correct 8 ms 35312 KB Output is correct
9 Correct 6 ms 35164 KB Output is correct
10 Correct 6 ms 35164 KB Output is correct
11 Correct 6 ms 35164 KB Output is correct
12 Correct 6 ms 35164 KB Output is correct
13 Correct 9 ms 35164 KB Output is correct
14 Correct 6 ms 35160 KB Output is correct
15 Correct 6 ms 35164 KB Output is correct
16 Correct 9 ms 35164 KB Output is correct
17 Correct 6 ms 35164 KB Output is correct
18 Correct 6 ms 35164 KB Output is correct
19 Correct 7 ms 35160 KB Output is correct
20 Correct 6 ms 35164 KB Output is correct
21 Correct 6 ms 35164 KB Output is correct
22 Correct 7 ms 35164 KB Output is correct
23 Correct 6 ms 35164 KB Output is correct
24 Correct 8 ms 35208 KB Output is correct
25 Correct 6 ms 35164 KB Output is correct
26 Correct 8 ms 35164 KB Output is correct
27 Correct 6 ms 35164 KB Output is correct
28 Correct 5 ms 35164 KB Output is correct
29 Correct 9 ms 35164 KB Output is correct
30 Correct 7 ms 35164 KB Output is correct
31 Correct 7 ms 35348 KB Output is correct
32 Correct 10 ms 35164 KB Output is correct
33 Correct 6 ms 35164 KB Output is correct
34 Correct 6 ms 35160 KB Output is correct
35 Correct 10 ms 35164 KB Output is correct
36 Correct 10 ms 35160 KB Output is correct
37 Correct 7 ms 35164 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35160 KB Output is correct
2 Correct 6 ms 35164 KB Output is correct
3 Correct 6 ms 35164 KB Output is correct
4 Correct 6 ms 35160 KB Output is correct
5 Correct 5 ms 35164 KB Output is correct
6 Correct 6 ms 35164 KB Output is correct
7 Correct 6 ms 35228 KB Output is correct
8 Correct 8 ms 35312 KB Output is correct
9 Correct 6 ms 35164 KB Output is correct
10 Correct 6 ms 35164 KB Output is correct
11 Correct 6 ms 35164 KB Output is correct
12 Correct 6 ms 35164 KB Output is correct
13 Correct 9 ms 35164 KB Output is correct
14 Correct 6 ms 35160 KB Output is correct
15 Correct 6 ms 35164 KB Output is correct
16 Correct 9 ms 35164 KB Output is correct
17 Correct 6 ms 35164 KB Output is correct
18 Correct 6 ms 35164 KB Output is correct
19 Correct 7 ms 35160 KB Output is correct
20 Correct 6 ms 35164 KB Output is correct
21 Correct 6 ms 35164 KB Output is correct
22 Correct 7 ms 35164 KB Output is correct
23 Correct 6 ms 35164 KB Output is correct
24 Correct 8 ms 35208 KB Output is correct
25 Correct 6 ms 35164 KB Output is correct
26 Correct 8 ms 35164 KB Output is correct
27 Correct 6 ms 35164 KB Output is correct
28 Correct 5 ms 35164 KB Output is correct
29 Correct 9 ms 35164 KB Output is correct
30 Correct 7 ms 35164 KB Output is correct
31 Correct 7 ms 35348 KB Output is correct
32 Correct 10 ms 35164 KB Output is correct
33 Correct 6 ms 35164 KB Output is correct
34 Correct 6 ms 35160 KB Output is correct
35 Correct 10 ms 35164 KB Output is correct
36 Correct 10 ms 35160 KB Output is correct
37 Correct 7 ms 35164 KB Output is correct
38 Correct 28 ms 37004 KB Output is correct
39 Correct 60 ms 65620 KB Output is correct
40 Correct 34 ms 36696 KB Output is correct
41 Correct 45 ms 36348 KB Output is correct
42 Correct 32 ms 36944 KB Output is correct
43 Correct 25 ms 36384 KB Output is correct
44 Correct 24 ms 35636 KB Output is correct
45 Correct 58 ms 50512 KB Output is correct
46 Correct 66 ms 50656 KB Output is correct
47 Correct 56 ms 58072 KB Output is correct
48 Correct 56 ms 57828 KB Output is correct
49 Correct 54 ms 50768 KB Output is correct
50 Correct 62 ms 50960 KB Output is correct
51 Correct 52 ms 52804 KB Output is correct
52 Correct 43 ms 52892 KB Output is correct
53 Correct 16 ms 36752 KB Output is correct
54 Correct 65 ms 50404 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35164 KB Output is correct
2 Correct 5 ms 35228 KB Output is correct
3 Correct 6 ms 35160 KB Output is correct
4 Correct 6 ms 35164 KB Output is correct
5 Correct 9 ms 35228 KB Output is correct
6 Correct 7 ms 35164 KB Output is correct
7 Correct 6 ms 35068 KB Output is correct
8 Correct 6 ms 35164 KB Output is correct
9 Correct 5 ms 35164 KB Output is correct
10 Correct 8 ms 35400 KB Output is correct
11 Correct 5 ms 35200 KB Output is correct
12 Correct 6 ms 35344 KB Output is correct
13 Correct 27 ms 35328 KB Output is correct
14 Correct 41 ms 35300 KB Output is correct
15 Correct 27 ms 35324 KB Output is correct
16 Correct 79 ms 52564 KB Output is correct
17 Correct 255 ms 62296 KB Output is correct
18 Correct 481 ms 73112 KB Output is correct
19 Correct 143 ms 54596 KB Output is correct
20 Correct 143 ms 54476 KB Output is correct
21 Correct 142 ms 54420 KB Output is correct
22 Correct 225 ms 62092 KB Output is correct
23 Correct 208 ms 61852 KB Output is correct
24 Correct 228 ms 62416 KB Output is correct
25 Correct 170 ms 62148 KB Output is correct
26 Correct 195 ms 62156 KB Output is correct
27 Correct 248 ms 67272 KB Output is correct
28 Correct 179 ms 70220 KB Output is correct
29 Correct 182 ms 64332 KB Output is correct
30 Correct 174 ms 60624 KB Output is correct
31 Correct 127 ms 61784 KB Output is correct
32 Correct 200 ms 60064 KB Output is correct
33 Correct 200 ms 61784 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 5 ms 35164 KB Output is correct
3 Correct 5 ms 35248 KB Output is correct
4 Correct 13 ms 35304 KB Output is correct
5 Correct 28 ms 35304 KB Output is correct
6 Correct 6 ms 35164 KB Output is correct
7 Correct 7 ms 35260 KB Output is correct
8 Correct 7 ms 35320 KB Output is correct
9 Correct 36 ms 37208 KB Output is correct
10 Correct 69 ms 65536 KB Output is correct
11 Correct 11 ms 35272 KB Output is correct
12 Correct 30 ms 35308 KB Output is correct
13 Correct 115 ms 71912 KB Output is correct
14 Correct 86 ms 72048 KB Output is correct
15 Correct 127 ms 76776 KB Output is correct
16 Correct 239 ms 92264 KB Output is correct
17 Correct 140 ms 79956 KB Output is correct
18 Correct 107 ms 72792 KB Output is correct
19 Correct 138 ms 78196 KB Output is correct
20 Correct 107 ms 78280 KB Output is correct
21 Correct 104 ms 78972 KB Output is correct
22 Correct 76 ms 69224 KB Output is correct
23 Correct 7 ms 35160 KB Output is correct
24 Correct 6 ms 35164 KB Output is correct
25 Correct 6 ms 35164 KB Output is correct
26 Correct 6 ms 35160 KB Output is correct
27 Correct 5 ms 35164 KB Output is correct
28 Correct 6 ms 35164 KB Output is correct
29 Correct 6 ms 35228 KB Output is correct
30 Correct 8 ms 35312 KB Output is correct
31 Correct 6 ms 35164 KB Output is correct
32 Correct 6 ms 35164 KB Output is correct
33 Correct 6 ms 35164 KB Output is correct
34 Correct 6 ms 35164 KB Output is correct
35 Correct 9 ms 35164 KB Output is correct
36 Correct 6 ms 35160 KB Output is correct
37 Correct 6 ms 35164 KB Output is correct
38 Correct 9 ms 35164 KB Output is correct
39 Correct 6 ms 35164 KB Output is correct
40 Correct 6 ms 35164 KB Output is correct
41 Correct 7 ms 35160 KB Output is correct
42 Correct 6 ms 35164 KB Output is correct
43 Correct 6 ms 35164 KB Output is correct
44 Correct 7 ms 35164 KB Output is correct
45 Correct 6 ms 35164 KB Output is correct
46 Correct 8 ms 35208 KB Output is correct
47 Correct 6 ms 35164 KB Output is correct
48 Correct 8 ms 35164 KB Output is correct
49 Correct 6 ms 35164 KB Output is correct
50 Correct 5 ms 35164 KB Output is correct
51 Correct 9 ms 35164 KB Output is correct
52 Correct 7 ms 35164 KB Output is correct
53 Correct 7 ms 35348 KB Output is correct
54 Correct 10 ms 35164 KB Output is correct
55 Correct 6 ms 35164 KB Output is correct
56 Correct 6 ms 35160 KB Output is correct
57 Correct 10 ms 35164 KB Output is correct
58 Correct 10 ms 35160 KB Output is correct
59 Correct 7 ms 35164 KB Output is correct
60 Correct 28 ms 37004 KB Output is correct
61 Correct 60 ms 65620 KB Output is correct
62 Correct 34 ms 36696 KB Output is correct
63 Correct 45 ms 36348 KB Output is correct
64 Correct 32 ms 36944 KB Output is correct
65 Correct 25 ms 36384 KB Output is correct
66 Correct 24 ms 35636 KB Output is correct
67 Correct 58 ms 50512 KB Output is correct
68 Correct 66 ms 50656 KB Output is correct
69 Correct 56 ms 58072 KB Output is correct
70 Correct 56 ms 57828 KB Output is correct
71 Correct 54 ms 50768 KB Output is correct
72 Correct 62 ms 50960 KB Output is correct
73 Correct 52 ms 52804 KB Output is correct
74 Correct 43 ms 52892 KB Output is correct
75 Correct 16 ms 36752 KB Output is correct
76 Correct 65 ms 50404 KB Output is correct
77 Correct 6 ms 35164 KB Output is correct
78 Correct 5 ms 35228 KB Output is correct
79 Correct 6 ms 35160 KB Output is correct
80 Correct 6 ms 35164 KB Output is correct
81 Correct 9 ms 35228 KB Output is correct
82 Correct 7 ms 35164 KB Output is correct
83 Correct 6 ms 35068 KB Output is correct
84 Correct 6 ms 35164 KB Output is correct
85 Correct 5 ms 35164 KB Output is correct
86 Correct 8 ms 35400 KB Output is correct
87 Correct 5 ms 35200 KB Output is correct
88 Correct 6 ms 35344 KB Output is correct
89 Correct 27 ms 35328 KB Output is correct
90 Correct 41 ms 35300 KB Output is correct
91 Correct 27 ms 35324 KB Output is correct
92 Correct 79 ms 52564 KB Output is correct
93 Correct 255 ms 62296 KB Output is correct
94 Correct 481 ms 73112 KB Output is correct
95 Correct 143 ms 54596 KB Output is correct
96 Correct 143 ms 54476 KB Output is correct
97 Correct 142 ms 54420 KB Output is correct
98 Correct 225 ms 62092 KB Output is correct
99 Correct 208 ms 61852 KB Output is correct
100 Correct 228 ms 62416 KB Output is correct
101 Correct 170 ms 62148 KB Output is correct
102 Correct 195 ms 62156 KB Output is correct
103 Correct 248 ms 67272 KB Output is correct
104 Correct 179 ms 70220 KB Output is correct
105 Correct 182 ms 64332 KB Output is correct
106 Correct 174 ms 60624 KB Output is correct
107 Correct 127 ms 61784 KB Output is correct
108 Correct 200 ms 60064 KB Output is correct
109 Correct 200 ms 61784 KB Output is correct
110 Correct 37 ms 35316 KB Output is correct
111 Correct 20 ms 35164 KB Output is correct
112 Correct 141 ms 71764 KB Output is correct
113 Correct 131 ms 62544 KB Output is correct
114 Correct 115 ms 67024 KB Output is correct
115 Correct 66 ms 51144 KB Output is correct
116 Correct 140 ms 54612 KB Output is correct
117 Correct 631 ms 83908 KB Output is correct
118 Correct 70 ms 50548 KB Output is correct
119 Correct 90 ms 50516 KB Output is correct
120 Correct 15 ms 36952 KB Output is correct
121 Correct 196 ms 56872 KB Output is correct
122 Correct 204 ms 57140 KB Output is correct
123 Correct 117 ms 65948 KB Output is correct
124 Correct 102 ms 65872 KB Output is correct
125 Correct 105 ms 66644 KB Output is correct
126 Correct 221 ms 87216 KB Output is correct
127 Correct 151 ms 74668 KB Output is correct
128 Correct 122 ms 75488 KB Output is correct
129 Correct 204 ms 74416 KB Output is correct
130 Correct 124 ms 75320 KB Output is correct