| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 848727 |
2023-09-13T11:52:28 Z |
danikoynov |
Jail (JOI22_jail) |
C++14 |
|
39 ms |
144088 KB |
/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 2e5 + 10;
int n, m, s[maxn], t[maxn], parent[maxn];
vector < int > adj[maxn], children[maxn];
void input()
{
cin >> n;
for (int i = 1; i < n; i ++)
{
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
cin >> m;
for (int i = 1; i <= m; i ++)
{
cin >> s[i] >> t[i];
}
}
int tin[maxn], tout[maxn], occ[2 * maxn], depth[maxn], timer;
int sub[maxn], heavy[maxn];
void euler(int v = 1, int p = -1)
{
tin[v] = ++ timer;
occ[timer] = v;
sub[v] = 1;
heavy[v] = -1;
parent[v] = p;
for (int u : adj[v])
{
if (u == p)
continue;
children[v].push_back(u);
depth[u] = depth[v] + 1;
euler(u, v);
if (heavy[v] == -1 || sub[u] > sub[heavy[v]])
heavy[v] = u;
sub[v] += sub[u];
occ[++ timer] = v;
}
tout[v] = timer;
}
const int maxlog = 20;
int dp[maxlog][maxn * 2], lg[2 * maxn];
void build_sparse_table()
{
for (int i = 1; i <= timer; i ++)
{
dp[0][i] = occ[i];
lg[i] = lg[i / 2] + 1;
}
for (int j = 1; j < lg[timer]; j ++)
{
for (int i = 1; i <= timer - (1 << j) + 1; i ++)
{
dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
if (depth[dp[j - 1][i]] < depth[dp[j][i]])
dp[j][i] = dp[j - 1][i];
}
}
}
int get_lca(int v, int u)
{
int l = tin[v], r = tin[u];
if (l > r)
swap(l, r);
int len = lg[r - l + 1] - 1;
int lca = dp[len][r - (1 << len) + 1];
if (depth[dp[len][l]] < depth[lca])
lca = dp[len][l];
return lca;
}
vector < int > graph[10 * maxn];
bool is_cycle;
bool in_subtree(int v, int u)
{
return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
bool on_path(int v, int u, int w)
{
int lca = get_lca(v, u);
if (in_subtree(lca, w) && in_subtree(w, v))
return true;
if (in_subtree(lca, w) && in_subtree(w, u))
return true;
return false;
}
void add_edge(int v, int u)
{
graph[v].push_back(u);
///cout << "edge " << v << " " << u << endl;
}
void check_prisoners(int i, int j)
{
/**if (on_path(s[i], t[i], s[j]) && on_path(s[i], t[i], t[j]))
{
is_cycle = true;
return;
}*/
if (on_path(s[i], t[i], s[j]))
{
add_edge(i, j);
///graph[i].push_back(j);
return;
}
if (on_path(s[i], t[i], t[j]))
{
add_edge(j, i);
///graph[j].push_back(i);
return;
}
}
vector < pair < int, int > > link[maxn];
set < pair < int, int > > loc_set[maxn];
bool cmp(pair < int, int > di, pair < int, int > dj)
{
int i = di.second, j = dj.second;
int d1 = depth[s[i]] + depth[t[i]] - 2 * depth[get_lca(s[i], t[i])];
int d2 = depth[s[j]] + depth[t[j]] - 2 * depth[get_lca(s[j], t[j])];
return d1 > d2;
}
bool check_range(int idx, int left, int right)
{
pair < int, int > cur = {left, -1};
set < pair < int, int > > :: iterator it = loc_set[idx].lower_bound(cur);
if (it == loc_set[idx].end())
return false;
if (it -> first <= right)
return true;
return false;
}
int find_child(int v, int u)
{
int lf = 0, rf = (int)(children[v].size()) - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (tout[children[v][mf]] < tin[u])
lf = mf + 1;
else
rf = mf - 1;
}
return children[v][lf];
}
void dfs(int v, int p)
{
for (int u : adj[v])
{
if (u == p)
continue;
dfs(u, v);
if (loc_set[u].size() > loc_set[v].size())
swap(loc_set[u], loc_set[v]);
for (pair < int, int > cur : loc_set[u])
{
pair < int, int > par = {tin[s[cur.second]], cur.second};
if (tin[s[cur.second]] == cur.first)
par.first = tin[t[cur.second]];
if (loc_set[v].find(par) != loc_set[v].end())
loc_set[v].erase(par);
else
loc_set[v].insert(cur);
}
}
sort(link[v].begin(), link[v].end(), cmp);
for (pair < int, int > cur : link[v])
{
pair < int, int > par = {tin[s[cur.second]], cur.second};
if (tin[s[cur.second]] == cur.first)
par.first = tin[t[cur.second]];
///cout << "here " << cur.first << " " << cur.second << " " << par.first << " " << par.second << " " << tin[s[cur.second]] << endl;
if (loc_set[v].find(par) != loc_set[v].end())
{
loc_set[v].erase(par);
continue;
}
int idx = cur.second, u = s[idx];
if (u == v)
u = t[idx];
if (!in_subtree(u, v))
{
if (check_range(v, tin[u], tout[u]))
is_cycle = true;
}
else
{
int child = find_child(u, v);
///cout << "HERE " << child << " " << u << endl;
if (check_range(v, 1, tin[child] - 1) || check_range(v, tout[child] + 1, timer))
{
///cout << "FOUND CYCLE " << v << " " << u << " " << child << endl;
is_cycle = true;
}
}
loc_set[v].insert(cur);
}
/**cout << v << " : " << p << endl;
for (pair < int, int > cur : loc_set[v])
cout << cur.first << " " << cur.second << endl;
cout << "cycle " << is_cycle << endl;
cout << "-------------" << endl;*/
}
struct chain
{
int top, left, right;
} ch[maxn];
int ord[maxn], ch_idx[maxn], ch_cnt, to, ch_pos[maxn];
void hld(int v)
{
ch_idx[v] = ch_cnt;
ord[++ to] = v;
ch[ch_idx[v]].right = to;
ch_pos[v] = to;
if (heavy[v] != -1)
hld(heavy[v]);
for (int u : children[v])
{
if (u == heavy[v])
continue;
ch_cnt ++;
ch[ch_cnt].top = v;
ch[ch_cnt].left = to + 1;
ch[ch_cnt].right = to;
hld(u);
}
}
vector < int > ver_start[maxn], ver_end[maxn], ftk[4 * maxn]; /// might be replaced
void build_forward_tree(int root, int left, int right)
{
ftk[root].clear();
///cout << root + m << " : " << left << " " << right << endl;
if (left == right)
{
for (int v : ver_start[left])
ftk[root].push_back(v);
///for (int v : ver_start[left])
/// add_edge(root + m, v);
return;
}
int mid = (left + right) / 2;
///add_edge(root + m, root * 2 + m);
///add_edge(root + m, root * 2 + 1 + m);
///graph[root + m].push_back(root * 2 + m);
///graph[root + m].push_back(root * 2 + 1 + m);
build_forward_tree(root * 2, left, mid);
build_forward_tree(root * 2 + 1, mid + 1, right);
}
vector < int > bkt[maxn * 4];
void build_backward_tree(int root, int left, int right)
{
bkt[root].clear();
if (left == right)
{
for (int v : ver_end[left])
{
bkt[root].push_back(v);
///add_edge(v, root + m + 4 * n);
///graph[v].push_back(root + m + 4 * n);
///cout << v << " here " << left << endl;
}
return;
}
int mid = (left + right) / 2;
///add_edge(root * 2 + m + 4 * n, root + m + 4 * n);
///add_edge(root * 2 + 1 + m + 4 * n, root + m + 4 * n);
///graph[root * 2 + m + 4 * n].push_back(root + m + 4 * n);
///graph[root * 2 + 1 + m + 4 * n].push_back(root + m + 4 * n);
build_backward_tree(root * 2, left, mid);
build_backward_tree(root * 2 + 1, mid + 1, right);
for (int v : bkt[root * 2])
bkt[root].push_back(v);
for (int v : bkt[root * 2 + 1])
bkt[root].push_back(v);
///for (int v : bkt[root])
/// add_edge(v, root + m + 4 * n);
}
void add_forward(int root, int left, int right, int qleft, int qright, int val)
{
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
for (int cur : ftk[root])
{
//cout << "forward" << endl;
add_edge(val, cur);
}
///add_edge(val, root + m);
///graph[val].push_back(root + m);
return;
}
int mid = (left + right) / 2;
add_forward(root * 2, left, mid, qleft, qright, val);
add_forward(root * 2 + 1, mid + 1, right, qleft, qright, val);
}
void add_backward(int root, int left, int right, int qleft, int qright, int val)
{
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
for (int cur : bkt[root])
{
///cout << "backward" << endl;
add_edge(cur, val);
}
///add_edge(root + m + 4 * n, val);
///graph[root + m + 4 * n].push_back(val);
return;
}
int mid = (left + right) / 2;
add_backward(root * 2, left, mid, qleft, qright, val);
add_backward(root * 2 + 1, mid + 1, right, qleft, qright, val);
}
void add_path_forward(int v, int lca, int idx)
{
while(ch_idx[v] != ch_idx[lca])
{
add_forward(1, 1, n, ch[ch_idx[v]].left, ch_pos[v], idx);
///add_backward(1, 1, n, ch[ch_idx[v]].left, ch_pos[v], idx);
v = ch[ch_idx[v]].top;
}
///cout << "idx " << idx << " " << ch_pos[lca] << " " << ch_pos[v] << endl;
add_forward(1, 1, n, ch_pos[lca], ch_pos[v], idx);
///add_backward(1, 1, n, ch_pos[lca], ch_pos[v], idx);
}
void add_path_backward(int v, int lca, int idx)
{
while(ch_idx[v] != ch_idx[lca])
{
///add_forward(1, 1, n, ch[ch_idx[v]].left, ch_pos[v], idx);
//cout << "range " << ch[ch_idx[v]].left << " " << ch_pos[v] << " " << ch[ch_idx[v]].top << " " << ch_pos[ch[ch_idx[v]].top] << endl;
add_backward(1, 1, n, ch[ch_idx[v]].left, ch_pos[v], idx);
v = ch[ch_idx[v]].top;
}
///cout << "idx " << idx << " " << ch_pos[lca] << " " << ch_pos[v] << endl;
///cout << "final range " << ch_pos[lca] << " " << ch_pos[v] << endl;
///add_forward(1, 1, n, ch_pos[lca], ch_pos[v], idx);
add_backward(1, 1, n, ch_pos[lca], ch_pos[v], idx);
}
void build_graph()
{
for (int i = 1; i <= m; i ++)
{
link[s[i]].push_back({tin[t[i]], i});
link[t[i]].push_back({tin[s[i]], i});
ver_start[ch_pos[s[i]]].push_back(i);
ver_end[ch_pos[t[i]]].push_back(i);
}
dfs(1, -1);
ch_cnt = 0;
to = 0;
ch[++ ch_cnt].top = 0;
ch[ch_cnt].left = 1;
ch[ch_cnt].right = 0;
///ch_pos[1] = 1;
hld(1);
build_backward_tree(1, 1, n);
build_forward_tree(1, 1, n);
for (int i = 1; i <= m; i ++)
{
int lca = get_lca(s[i], t[i]);
if (depth[s[i]] + depth[t[i]] - 2 * depth[lca] != 1)
{
int v = s[i], u = t[i];
if (lca != v && lca != u)
{
v = parent[v];
u = parent[u];
}
else if (lca == v)
{
v = find_child(v, u);
u = parent[u];
}
else if (lca == u)
{
u = find_child(u, v);
v = parent[v];
}
///cout << v << " ---- " << u << endl;
lca = get_lca(v, u);
///cout << "path " << v << " : " << u << endl;
add_path_forward(v, lca, i);
if (u != lca)
add_path_forward(u, find_child(lca, u), i);
add_path_backward(v, lca, i);
if (u != lca)
add_path_backward(u, find_child(lca, u), i);
}
for (pair < int, int > cur : link[s[i]])
{
if (i != cur.second)
check_prisoners(i, cur.second);
}
for (pair < int, int > cur : link[t[i]])
{
if (i != cur.second)
check_prisoners(i, cur.second);
}
}
/**for (int i = 1; i <= m; i ++)
{
for (int j = 1; j <= m; j ++)
{
if (i != j)
check_prisoners(i, j);
}
}*/
}
int used[maxn];
void check_dag(int v)
{
used[v] = 1;
for (int u : graph[v])
{
if (used[u] == 2)
continue;
///cout << v << " : " << u << endl;
if (used[u] == 1)
is_cycle = 1;
else
{
check_dag(u);
}
}
used[v] = 2;
}
void check_graph()
{
for (int i = 1; i <= m + 8 * n; i ++)
{
if (!used[i])
check_dag(i);
}
if (is_cycle)
cout << "No" << endl;
else
cout << "Yes" << endl;
}
void clear_data()
{
is_cycle = false;
for (int i = 1; i <= m + 8 * n; i ++)
graph[i].clear(), used[i] = 0;
for (int i = 1; i <= n; i ++)
{
ord[i] = 0;
ch_pos[i] = 0;
ch_idx[i] = 0;
}
to = 0;
ch_cnt = 0;
for (int i = 1; i <= 2 * n; i ++)
{
adj[i].clear();
link[i].clear();
ver_start[i].clear();
ver_end[i].clear();
children[i].clear();
loc_set[i].clear();
}
timer = 0;
}
void solve()
{
input();
euler();
build_sparse_table();
build_graph();
check_graph();
clear_data();
}
int main()
{
speed();
///freopen("test.txt", "r", stdin);
int q;
cin >> q;
while(q --)
solve();
return 0;
}
/**
1
7
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7
1
4
1 2
2 3
3 4
2
1 3
2 4
1
250
1 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
3 25
1 26
26 27
27 28
28 29
29 30
30 31
5 31
1 32
32 33
33 34
34 35
35 36
36 37
37 38
7 38
2 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
4 46
2 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
12 55
2 56
56 57
57 58
58 59
59 60
60 61
61 62
62 63
14 63
3 64
64 65
65 66
66 67
67 68
68 69
69 70
70 71
71 72
72 73
73 74
74 75
75 76
76 77
4 77
3 78
78 79
79 80
80 81
81 82
82 83
83 84
84 85
85 86
86 87
8 87
4 88
88 89
89 90
90 91
91 92
92 93
93 94
94 95
11 95
5 96
96 97
97 98
98 99
99 100
6 100
8 101
101 102
102 103
103 104
104 105
105 106
106 107
107 108
108 109
109 110
9 110
8 111
111 112
112 113
113 114
114 115
115 116
116 117
117 118
118 119
119 120
10 120
12 121
121 122
122 123
123 124
124 125
125 126
13 126
65 127
118 128
84 129
110 130
8 131
14 132
129 133
106 134
3 135
7 136
27 137
9 138
18 139
44 140
8 141
97 142
20 143
115 144
120 145
5 146
69 147
47 148
59 149
1 150
34 151
14 152
45 153
31 154
96 155
108 156
64 157
87 158
30 159
56 160
86 161
88 162
13 163
82 164
140 165
25 166
13 167
62 168
107 169
34 170
10 171
108 172
86 173
30 174
150 175
131 176
14 177
154 178
142 179
55 180
35 181
16 182
75 183
97 184
114 185
155 186
137 187
17 188
183 189
123 190
140 191
172 192
94 193
132 194
57 195
173 196
46 197
174 198
179 199
65 200
183 201
29 202
201 203
124 204
106 205
169 206
177 207
178 208
78 209
119 210
129 211
50 212
41 213
73 214
161 215
78 216
50 217
98 218
190 219
105 220
215 221
49 222
39 223
217 224
166 225
165 226
198 227
170 228
65 229
83 230
165 231
121 232
209 233
213 234
96 235
235 236
70 237
105 238
3 239
4 240
41 241
178 242
242 243
199 244
156 245
178 246
122 247
188 248
211 249
71 250
2
1 2
7 1
1
250
1 15
15 16
16 17
17 18
18 19
19 20
3 20
1 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
5 31
1 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
7 49
2 50
50 51
51 52
52 53
53 54
54 55
55 56
56 57
57 58
4 58
2 59
59 60
60 61
12 61
2 62
62 63
63 64
14 64
3 65
65 66
66 67
67 68
68 69
69 70
70 71
4 71
3 72
72 73
73 74
74 75
75 76
76 77
77 78
78 79
79 80
80 81
81 82
8 82
4 83
83 84
84 85
85 86
86 87
87 88
88 89
89 90
90 91
91 92
11 92
5 93
93 94
94 95
95 96
96 97
97 98
98 99
6 99
8 100
100 101
101 102
102 103
103 104
104 105
105 106
106 107
9 107
8 108
108 109
109 110
110 111
111 112
112 113
113 114
114 115
115 116
116 117
10 117
12 118
118 119
119 120
120 121
121 122
122 123
123 124
124 125
125 126
13 126
79 127
8 128
50 129
126 130
104 131
24 132
66 133
115 134
123 135
86 136
110 137
5 138
55 139
137 140
79 141
50 142
1 143
115 144
106 145
143 146
24 147
54 148
66 149
76 150
114 151
140 152
39 153
152 154
3 155
151 156
127 157
48 158
60 159
9 160
87 161
79 162
54 163
107 164
117 165
120 166
27 167
86 168
145 169
161 170
159 171
57 172
110 173
134 174
56 175
101 176
3 177
33 178
12 179
28 180
50 181
180 182
58 183
40 184
147 185
105 186
73 187
1 188
188 189
143 190
84 191
176 192
119 193
184 194
130 195
128 196
106 197
188 198
175 199
72 200
39 201
141 202
195 203
114 204
172 205
152 206
202 207
113 208
25 209
164 210
131 211
10 212
180 213
41 214
135 215
208 216
8 217
27 218
202 219
145 220
136 221
219 222
91 223
214 224
38 225
202 226
117 227
150 228
118 229
112 230
209 231
183 232
61 233
84 234
188 235
6 236
36 237
72 238
90 239
225 240
223 241
71 242
143 243
105 244
161 245
234 246
123 247
165 248
179 249
177 250
2
1 2
6 14
2
1 2
8 9
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
135768 KB |
Output is correct |
| 2 |
Correct |
28 ms |
135772 KB |
Output is correct |
| 3 |
Correct |
26 ms |
131568 KB |
Output is correct |
| 4 |
Incorrect |
39 ms |
141912 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
135768 KB |
Output is correct |
| 2 |
Correct |
26 ms |
131672 KB |
Output is correct |
| 3 |
Incorrect |
29 ms |
144088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
135768 KB |
Output is correct |
| 2 |
Correct |
26 ms |
131672 KB |
Output is correct |
| 3 |
Incorrect |
29 ms |
144088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
135768 KB |
Output is correct |
| 2 |
Correct |
26 ms |
131672 KB |
Output is correct |
| 3 |
Incorrect |
29 ms |
144088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
135768 KB |
Output is correct |
| 2 |
Correct |
26 ms |
131672 KB |
Output is correct |
| 3 |
Incorrect |
29 ms |
144088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
135768 KB |
Output is correct |
| 2 |
Correct |
27 ms |
135772 KB |
Output is correct |
| 3 |
Correct |
27 ms |
135764 KB |
Output is correct |
| 4 |
Correct |
26 ms |
131672 KB |
Output is correct |
| 5 |
Incorrect |
34 ms |
137816 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
135768 KB |
Output is correct |
| 2 |
Correct |
28 ms |
135772 KB |
Output is correct |
| 3 |
Correct |
26 ms |
131568 KB |
Output is correct |
| 4 |
Incorrect |
39 ms |
141912 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
