#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ld long double
#define ll long long
mt19937 rnd(51);
const int N = 2.5e5 + 10, INF = 1e9;
vector<pair<int,int>> g[N], need1[N];
vector<int> sz(N), ans(N), val(N), fir(N), need2[N], arr, mas;
vector<bool> used(N), good(N);
struct Fenwick {
vector<int> t;
Fenwick(int n) {
t.resize(n);
}
void inc(int i, int d) {
for (; i < t.size(); i = (i | (i + 1))) {
t[i] += d;
}
}
int get(int r) {
int ans = 0;
for (; r >= 0; r = (r & (r + 1)) - 1) {
ans += t[r];
}
return ans;
}
} t(N);
void zhfs(int v, int p) {
sz[v] = 1;
for (auto to : g[v]) {
if (to.first != p && !used[to.first]) {
zhfs(to.first, v);
sz[v] += sz[to.first];
}
}
}
int find_centroid(int v, int p, int n) {
for (auto to : g[v]) {
if (to.first != p && !used[to.first] && sz[to.first] > n / 2) {
return find_centroid(to.first, v, n);
}
}
return v;
}
void dfs1(int v, int p, int last, int first_val) {
val[v] = last;
fir[v] = first_val;
good[v] = 1;
arr.pb(v);
for (auto to : g[v]) {
if (to.first != p && !used[to.first] && to.second > last) {
dfs1(to.first, v, to.second, (last == -INF ? to.second : first_val));
}
}
}
void walk(int v, int p) {
if (!good[v]) return;
t.inc(val[v], 1);
mas.pb(v);
for (auto to : g[v]) {
if (to.first != p && !used[to.first]) {
walk(to.first, v);
}
}
}
void dfs2(int v, int p, int last, int first_val) {
for (auto to : need1[v]) {
if (first_val == fir[to.first]) continue;
if (good[to.first] && max({first_val, val[to.first]}) < to.second && first_val < fir[to.first]) {
ans[to.second] = INF;
}
}
for (auto to : g[v]) {
if (to.first != p && !used[to.first] && to.second < last) {
dfs2(to.first, v, to.second, (last == INF ? to.second : first_val));
if (last == INF) {
walk(to.first, v);
}
}
}
for (auto to : need2[v]) {
if (first_val > to) continue;
ans[to] += t.get(to - 1) + 1;
}
}
void solve(int v) {
sort(g[v].begin(), g[v].end(), [&](pair<int,int> a, pair<int,int> b){return a.second > b.second;});
zhfs(v, -1);
arr.clear();
dfs1(v, -1, -INF, INF);
dfs2(v, -1, INF, -INF);
for (auto to : mas) {
t.inc(val[to], -1);
}
mas.clear();
for (auto to : arr) {
good[to] = 0;
}
used[v] = 1;
for (auto to : g[v]) {
if (!used[to.first]) {
solve(find_centroid(to.first, v, sz[to.first]));
}
}
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LCOAL
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
for (int i = 0; i < n + k - 1; i++) {
char c;
cin >> c;
if (c == 'S') {
int a, b;
cin >> a >> b;
a--, b--;
g[a].pb({b, i});
g[b].pb({a, i});
ans[i] = -1;
} else if (c == 'Q') {
int a, d;
cin >> a >> d;
a--, d--;
need1[d].pb({a, i});
ans[i] = INF + 1;
} else {
int d;
cin >> d;
d--;
need2[d].pb(i);
}
}
zhfs(0, -1);
solve(find_centroid(0, -1, n));
for (int i = 0; i < n + k - 1; i++) {
if (ans[i] == -1) continue;
if (ans[i] >= INF) {
if (ans[i] == INF) {
cout << "yes\n";
} else {
cout << "no\n";
}
} else {
cout << ans[i] << endl;
}
}
return 0;
}
Compilation message
servers.cpp: In member function 'void Fenwick::inc(int, int)':
servers.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for (; i < t.size(); i = (i | (i + 1))) {
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
24788 KB |
Output is correct |
2 |
Correct |
39 ms |
25020 KB |
Output is correct |
3 |
Correct |
39 ms |
24888 KB |
Output is correct |
4 |
Correct |
40 ms |
25060 KB |
Output is correct |
5 |
Correct |
47 ms |
25292 KB |
Output is correct |
6 |
Correct |
44 ms |
25064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
24788 KB |
Output is correct |
2 |
Correct |
39 ms |
25020 KB |
Output is correct |
3 |
Correct |
39 ms |
24888 KB |
Output is correct |
4 |
Correct |
40 ms |
25060 KB |
Output is correct |
5 |
Correct |
47 ms |
25292 KB |
Output is correct |
6 |
Correct |
44 ms |
25064 KB |
Output is correct |
7 |
Correct |
39 ms |
24820 KB |
Output is correct |
8 |
Correct |
123 ms |
24656 KB |
Output is correct |
9 |
Correct |
140 ms |
24528 KB |
Output is correct |
10 |
Correct |
119 ms |
24632 KB |
Output is correct |
11 |
Correct |
110 ms |
24892 KB |
Output is correct |
12 |
Correct |
121 ms |
24868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
24788 KB |
Output is correct |
2 |
Correct |
162 ms |
31672 KB |
Output is correct |
3 |
Correct |
154 ms |
31680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
24788 KB |
Output is correct |
2 |
Correct |
162 ms |
31672 KB |
Output is correct |
3 |
Correct |
154 ms |
31680 KB |
Output is correct |
4 |
Correct |
43 ms |
24728 KB |
Output is correct |
5 |
Correct |
200 ms |
31448 KB |
Output is correct |
6 |
Correct |
247 ms |
30340 KB |
Output is correct |
7 |
Correct |
261 ms |
31988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
24824 KB |
Output is correct |
2 |
Correct |
232 ms |
36940 KB |
Output is correct |
3 |
Correct |
275 ms |
36960 KB |
Output is correct |
4 |
Correct |
223 ms |
37388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
24824 KB |
Output is correct |
2 |
Correct |
232 ms |
36940 KB |
Output is correct |
3 |
Correct |
275 ms |
36960 KB |
Output is correct |
4 |
Correct |
223 ms |
37388 KB |
Output is correct |
5 |
Correct |
41 ms |
24816 KB |
Output is correct |
6 |
Correct |
351 ms |
37312 KB |
Output is correct |
7 |
Correct |
312 ms |
37852 KB |
Output is correct |
8 |
Correct |
393 ms |
36896 KB |
Output is correct |
9 |
Correct |
359 ms |
36816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
24780 KB |
Output is correct |
2 |
Correct |
223 ms |
31024 KB |
Output is correct |
3 |
Correct |
197 ms |
30512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
24780 KB |
Output is correct |
2 |
Correct |
223 ms |
31024 KB |
Output is correct |
3 |
Correct |
197 ms |
30512 KB |
Output is correct |
4 |
Correct |
41 ms |
24800 KB |
Output is correct |
5 |
Correct |
304 ms |
31516 KB |
Output is correct |
6 |
Correct |
318 ms |
30788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
24844 KB |
Output is correct |
2 |
Correct |
286 ms |
37008 KB |
Output is correct |
3 |
Correct |
267 ms |
36944 KB |
Output is correct |
4 |
Correct |
260 ms |
37364 KB |
Output is correct |
5 |
Correct |
33 ms |
24776 KB |
Output is correct |
6 |
Correct |
205 ms |
31020 KB |
Output is correct |
7 |
Correct |
236 ms |
30412 KB |
Output is correct |
8 |
Correct |
259 ms |
31272 KB |
Output is correct |
9 |
Correct |
270 ms |
31060 KB |
Output is correct |
10 |
Correct |
438 ms |
34348 KB |
Output is correct |
11 |
Correct |
348 ms |
33268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
24844 KB |
Output is correct |
2 |
Correct |
286 ms |
37008 KB |
Output is correct |
3 |
Correct |
267 ms |
36944 KB |
Output is correct |
4 |
Correct |
260 ms |
37364 KB |
Output is correct |
5 |
Correct |
33 ms |
24776 KB |
Output is correct |
6 |
Correct |
205 ms |
31020 KB |
Output is correct |
7 |
Correct |
236 ms |
30412 KB |
Output is correct |
8 |
Correct |
259 ms |
31272 KB |
Output is correct |
9 |
Correct |
270 ms |
31060 KB |
Output is correct |
10 |
Correct |
438 ms |
34348 KB |
Output is correct |
11 |
Correct |
348 ms |
33268 KB |
Output is correct |
12 |
Correct |
46 ms |
24812 KB |
Output is correct |
13 |
Correct |
397 ms |
37308 KB |
Output is correct |
14 |
Correct |
351 ms |
37852 KB |
Output is correct |
15 |
Correct |
464 ms |
36812 KB |
Output is correct |
16 |
Correct |
446 ms |
36852 KB |
Output is correct |
17 |
Correct |
58 ms |
24772 KB |
Output is correct |
18 |
Correct |
347 ms |
31424 KB |
Output is correct |
19 |
Correct |
345 ms |
30776 KB |
Output is correct |
20 |
Correct |
353 ms |
31660 KB |
Output is correct |
21 |
Correct |
421 ms |
31636 KB |
Output is correct |
22 |
Correct |
562 ms |
33728 KB |
Output is correct |
23 |
Correct |
687 ms |
34432 KB |
Output is correct |
24 |
Correct |
636 ms |
36976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
24868 KB |
Output is correct |
2 |
Correct |
54 ms |
25028 KB |
Output is correct |
3 |
Correct |
44 ms |
24860 KB |
Output is correct |
4 |
Correct |
53 ms |
25036 KB |
Output is correct |
5 |
Correct |
69 ms |
25232 KB |
Output is correct |
6 |
Correct |
53 ms |
25120 KB |
Output is correct |
7 |
Correct |
54 ms |
24824 KB |
Output is correct |
8 |
Correct |
243 ms |
31624 KB |
Output is correct |
9 |
Correct |
211 ms |
31680 KB |
Output is correct |
10 |
Correct |
45 ms |
24776 KB |
Output is correct |
11 |
Correct |
353 ms |
36948 KB |
Output is correct |
12 |
Correct |
380 ms |
36956 KB |
Output is correct |
13 |
Correct |
278 ms |
37404 KB |
Output is correct |
14 |
Correct |
41 ms |
24776 KB |
Output is correct |
15 |
Correct |
286 ms |
31024 KB |
Output is correct |
16 |
Correct |
313 ms |
30444 KB |
Output is correct |
17 |
Correct |
294 ms |
31260 KB |
Output is correct |
18 |
Correct |
347 ms |
31088 KB |
Output is correct |
19 |
Correct |
465 ms |
34316 KB |
Output is correct |
20 |
Correct |
396 ms |
33284 KB |
Output is correct |
21 |
Correct |
205 ms |
31260 KB |
Output is correct |
22 |
Correct |
221 ms |
31032 KB |
Output is correct |
23 |
Correct |
215 ms |
30672 KB |
Output is correct |
24 |
Correct |
227 ms |
30668 KB |
Output is correct |
25 |
Correct |
334 ms |
34556 KB |
Output is correct |
26 |
Correct |
247 ms |
29472 KB |
Output is correct |
27 |
Correct |
297 ms |
29380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
24868 KB |
Output is correct |
2 |
Correct |
54 ms |
25028 KB |
Output is correct |
3 |
Correct |
44 ms |
24860 KB |
Output is correct |
4 |
Correct |
53 ms |
25036 KB |
Output is correct |
5 |
Correct |
69 ms |
25232 KB |
Output is correct |
6 |
Correct |
53 ms |
25120 KB |
Output is correct |
7 |
Correct |
54 ms |
24824 KB |
Output is correct |
8 |
Correct |
243 ms |
31624 KB |
Output is correct |
9 |
Correct |
211 ms |
31680 KB |
Output is correct |
10 |
Correct |
45 ms |
24776 KB |
Output is correct |
11 |
Correct |
353 ms |
36948 KB |
Output is correct |
12 |
Correct |
380 ms |
36956 KB |
Output is correct |
13 |
Correct |
278 ms |
37404 KB |
Output is correct |
14 |
Correct |
41 ms |
24776 KB |
Output is correct |
15 |
Correct |
286 ms |
31024 KB |
Output is correct |
16 |
Correct |
313 ms |
30444 KB |
Output is correct |
17 |
Correct |
294 ms |
31260 KB |
Output is correct |
18 |
Correct |
347 ms |
31088 KB |
Output is correct |
19 |
Correct |
465 ms |
34316 KB |
Output is correct |
20 |
Correct |
396 ms |
33284 KB |
Output is correct |
21 |
Correct |
205 ms |
31260 KB |
Output is correct |
22 |
Correct |
221 ms |
31032 KB |
Output is correct |
23 |
Correct |
215 ms |
30672 KB |
Output is correct |
24 |
Correct |
227 ms |
30668 KB |
Output is correct |
25 |
Correct |
334 ms |
34556 KB |
Output is correct |
26 |
Correct |
247 ms |
29472 KB |
Output is correct |
27 |
Correct |
297 ms |
29380 KB |
Output is correct |
28 |
Correct |
40 ms |
24788 KB |
Output is correct |
29 |
Correct |
118 ms |
24656 KB |
Output is correct |
30 |
Correct |
109 ms |
24420 KB |
Output is correct |
31 |
Correct |
123 ms |
24692 KB |
Output is correct |
32 |
Correct |
126 ms |
24908 KB |
Output is correct |
33 |
Correct |
109 ms |
24620 KB |
Output is correct |
34 |
Correct |
45 ms |
24780 KB |
Output is correct |
35 |
Correct |
176 ms |
31460 KB |
Output is correct |
36 |
Correct |
232 ms |
30260 KB |
Output is correct |
37 |
Correct |
265 ms |
32068 KB |
Output is correct |
38 |
Correct |
41 ms |
25680 KB |
Output is correct |
39 |
Correct |
316 ms |
40500 KB |
Output is correct |
40 |
Correct |
325 ms |
40860 KB |
Output is correct |
41 |
Correct |
386 ms |
39492 KB |
Output is correct |
42 |
Correct |
397 ms |
39500 KB |
Output is correct |
43 |
Correct |
41 ms |
25624 KB |
Output is correct |
44 |
Correct |
319 ms |
34416 KB |
Output is correct |
45 |
Correct |
291 ms |
33668 KB |
Output is correct |
46 |
Correct |
302 ms |
34568 KB |
Output is correct |
47 |
Correct |
335 ms |
34576 KB |
Output is correct |
48 |
Correct |
430 ms |
36384 KB |
Output is correct |
49 |
Correct |
535 ms |
37316 KB |
Output is correct |
50 |
Correct |
389 ms |
36976 KB |
Output is correct |
51 |
Correct |
268 ms |
32828 KB |
Output is correct |
52 |
Correct |
279 ms |
32832 KB |
Output is correct |
53 |
Correct |
236 ms |
32388 KB |
Output is correct |
54 |
Correct |
250 ms |
33092 KB |
Output is correct |
55 |
Correct |
269 ms |
32092 KB |
Output is correct |
56 |
Correct |
236 ms |
33028 KB |
Output is correct |
57 |
Correct |
335 ms |
35392 KB |
Output is correct |
58 |
Correct |
401 ms |
33264 KB |
Output is correct |
59 |
Correct |
298 ms |
32972 KB |
Output is correct |