#include <bits/stdc++.h>
using namespace std;
const int N = 120'000 + 10,
MAX = 1'000'000;
int n, k;
vector<pair<int, int>> ad[N];
vector<tuple<int, int, int>> Q;
namespace group1 {
int st[N], ed[N], it;
int f[N][18], increase[N][18], decrease[N][18];
void dfs(int u, int p = -1) {
st[u] = ++it;
for (int i = 1; i <= 17; ++i) {
f[u][i] = f[f[u][i - 1]][i - 1];
if (increase[u][i - 1] != -1 && increase[f[u][i - 1]][i - 1] != -1) {
if (increase[u][i - 1] < increase[f[u][i - 1]][0])
increase[u][i] = increase[f[u][i - 1]][i - 1];
}
if (decrease[u][i - 1] != -1 && decrease[f[u][i - 1]][i - 1] != -1) {
if (decrease[u][i - 1] > decrease[f[u][i - 1]][0])
decrease[u][i] = decrease[f[u][i - 1]][i - 1];
}
}
for (const auto& [v, w] : ad[u]) {
if (v == p) continue;
f[v][0] = u;
increase[v][0] = decrease[v][0] = w;
dfs(v, u);
}
ed[u] = it;
}
inline bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
void init() {
memset(increase, 63, sizeof increase);
dfs(f[1][0] = 1);
}
int get(int u, int v) {
int uwd = 0, dwd = MAX, ma = 0;
for (int i = 17; i >= 0; --i) {
if (anc(f[u][i], v)) continue;
if (uwd >= increase[u][0]) return MAX;
uwd = increase[u][i];
u = f[u][i];
}
if (!anc(u, v)) {
if (uwd >= increase[u][0]) return MAX;
uwd = increase[u][0];
u = f[u][0];
} ma = uwd;
for (int i = 17; i >= 0; --i) {
if (anc(f[v][i], u)) continue;
if (dwd <= decrease[v][0]) return MAX;
dwd = decrease[v][i];
ma = max(ma, decrease[v][0]);
v = f[v][i];
}
if (v != u) {
if (dwd <= decrease[v][0]) return MAX;
dwd = decrease[v][0];
ma = max(ma, decrease[v][0]);
v = f[v][0];
}
return uwd < dwd ? ma : MAX;
}
}
namespace group2 {
int sz[N];
void dfs0(int u, int p = -1) {
for (const auto& [v, w] : ad[u]) {
if (v == p) continue;
dfs0(v, u);
sz[u] += sz[v] + 1;
}
}
int st[N], ed[N], rvs[N], it;
int head[N], par[N];
int minimum[N];
void hld(int u, int p = -1) {
st[u] = ++it; rvs[u] = it;
if (!head[u]) head[u] = u;
sort(ad[u].begin(), ad[u].end(), [&](const auto& a, const auto& b) {
return sz[a.first] > sz[b.first];
});
int heavy = 0;
for (const auto& [v, w] : ad[u]) {
if (v == p) continue;
if (!heavy) heavy = head[v] = head[u], minimum[u] = w;
par[v] = u;
hld(v, u);
}
ed[u] = it;
}
struct IT {
vector<int> rrh;
vector<int> f, lazy;
inline void push(int s, int l, int r) {
int mid = (l + r) >> 1;
f[s << 1] += (mid - l + 1) * lazy[s]; f[s << 1 | 1] += (r - mid) * lazy[s];
lazy[s << 1] += lazy[s]; lazy[s << 1 | 1] += lazy[s];
lazy[s] = 0;
}
void update(int s, int l, int r, int u, int v, int x) {
if (v < l || u > r) return;
if (u <= l && r <= v) {
f[s] += (r - l + 1) * x;
lazy[s] += x;
return;
}
push(s, l, r);
int mid = (l + r) >> 1;
update(s << 1, l, mid, u, v, x); update(s << 1 | 1, mid + 1, r, u, v, x);
f[s] = f[s << 1] + f[s << 1 | 1];
}
int query(int s, int l, int r, int u, int v) {
if (v < l || u > r) return 0;
if (u <= l && r <= v) return f[s];
push(s, l, r);
int mid = (l + r) >> 1;
return query(s << 1, l, mid, u, v) + query(s << 1 | 1, mid + 1, r, u, v);
}
void upd(int l, int r, int x) { update(1, 1, rrh.size(), l, r, x); }
int que(int l, int r) { return query(1, 1, rrh.size(), l, r); }
} T[N], D, E;
void init() {
dfs0(1); hld(par[1] = 1);
D.rrh = vector<int>(n);
E.rrh = vector<int>(n);
D.f = D.lazy = vector<int>(n + 10 << 2);
E.f = E.lazy = vector<int>(n + 10 << 2);
for (int u = 1; u <= n; ++u) {
for (const auto& [v, w] : ad[u])
if (par[v] == u) T[u].rrh.push_back(w);
sort(T[u].rrh.begin(), T[u].rrh.end());
T[u].f = T[u].lazy = vector<int>(T[u].rrh.size() + 10 << 2);
}
}
int cnt[N];
void add(int u, int v, int time) {
if (par[u] == v) swap(u, v);
int x = v;
for (int i = 17; i >= 0; --i) {
int moment = group1::get(group1::f[x][i], v);
if (moment <= time) x = group1::f[x][i];
}
while (head[v] != head[x]) {
int moment = group1::decrease[head[v]][0];
E.upd(st[head[v]], st[v] - 1, 1);
v = par[head[v]];
E.upd(st[v], st[v], 1); cnt[v] += 1;
D.upd(st[v], st[v], moment > minimum[v]);
int it = upper_bound(T[v].rrh.begin(), T[v].rrh.end(), moment) - T[v].rrh.begin();
T[v].upd(it, it, 1);
} E.upd(st[x], st[v] - 1, 1);
}
int get(int u, int time) {
int uwd = 0, x = u;
for (int i = 17; i >= 0; --i) {
if (group1::increase[x][i] > time || uwd > group1::increase[x][0]) continue;
uwd = group1::increase[x][i];
x = group1::f[x][i];
}
int ret = E.que(st[u], st[u]);
while (head[u] != head[x]) {
ret += st[u] - st[head[u]] + 1;
ret += D.que(st[head[u]], st[u] - 1);
int moment = group1::increase[head[u]][0];
u = par[head[u]];
if (moment < minimum[u]) ret += E.que(st[u], st[u]) - cnt[u];
int it = upper_bound(T[u].rrh.begin(), T[u].rrh.end(), moment) - T[u].rrh.begin() + 1;
ret += T[u].que(it, T[u].rrh.size());
} ret += D.que(st[x], st[u] - 1) + st[u] - st[x] + 1;
return ret;
}
};
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i < n + k; ++i) {
char type; cin >> type;
if (type == 'S') {
int a, b; cin >> a >> b;
ad[a].push_back({b, i});
ad[b].push_back({a, i});
Q.emplace_back(0, a, b);
}
if (type == 'Q') {
int a, d; cin >> a >> d;
Q.emplace_back(1, a, d);
}
if (type == 'C') {
int d; cin >> d;
Q.emplace_back(2, 0, d);
}
}
group1::init(); group2::init();
for (int i = 1; i < n + k; ++i) {
const auto& [type, a, b] = Q[i - 1];
if (!type) group2::add(a, b, i);
else if (type == 1) cout << (group1::get(b, a) <= i ? "yes" : "no") << "\n";
else cout << group2::get(b, i) << "\n";
}
}
Compilation message
servers.cpp: In function 'void group2::init()':
servers.cpp:147:34: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
147 | D.f = D.lazy = vector<int>(n + 10 << 2);
| ~~^~~~
servers.cpp:148:34: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
148 | E.f = E.lazy = vector<int>(n + 10 << 2);
| ~~^~~~
servers.cpp:154:56: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
154 | T[u].f = T[u].lazy = vector<int>(T[u].rrh.size() + 10 << 2);
| ~~~~~~~~~~~~~~~~^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
30068 KB |
Output is correct |
2 |
Correct |
34 ms |
34860 KB |
Output is correct |
3 |
Correct |
34 ms |
34812 KB |
Output is correct |
4 |
Correct |
41 ms |
34956 KB |
Output is correct |
5 |
Correct |
35 ms |
33028 KB |
Output is correct |
6 |
Correct |
33 ms |
34796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
30068 KB |
Output is correct |
2 |
Correct |
34 ms |
34860 KB |
Output is correct |
3 |
Correct |
34 ms |
34812 KB |
Output is correct |
4 |
Correct |
41 ms |
34956 KB |
Output is correct |
5 |
Correct |
35 ms |
33028 KB |
Output is correct |
6 |
Correct |
33 ms |
34796 KB |
Output is correct |
7 |
Correct |
25 ms |
29904 KB |
Output is correct |
8 |
Correct |
47 ms |
34320 KB |
Output is correct |
9 |
Correct |
48 ms |
34620 KB |
Output is correct |
10 |
Correct |
48 ms |
34512 KB |
Output is correct |
11 |
Correct |
45 ms |
32580 KB |
Output is correct |
12 |
Correct |
47 ms |
34532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
29904 KB |
Output is correct |
2 |
Correct |
379 ms |
105720 KB |
Output is correct |
3 |
Correct |
330 ms |
105972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
29904 KB |
Output is correct |
2 |
Correct |
379 ms |
105720 KB |
Output is correct |
3 |
Correct |
330 ms |
105972 KB |
Output is correct |
4 |
Correct |
24 ms |
30000 KB |
Output is correct |
5 |
Correct |
345 ms |
105840 KB |
Output is correct |
6 |
Correct |
341 ms |
105096 KB |
Output is correct |
7 |
Correct |
345 ms |
105212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
29900 KB |
Output is correct |
2 |
Correct |
338 ms |
118612 KB |
Output is correct |
3 |
Correct |
348 ms |
118472 KB |
Output is correct |
4 |
Correct |
296 ms |
118524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
29900 KB |
Output is correct |
2 |
Correct |
338 ms |
118612 KB |
Output is correct |
3 |
Correct |
348 ms |
118472 KB |
Output is correct |
4 |
Correct |
296 ms |
118524 KB |
Output is correct |
5 |
Correct |
25 ms |
29892 KB |
Output is correct |
6 |
Correct |
357 ms |
118008 KB |
Output is correct |
7 |
Correct |
322 ms |
118316 KB |
Output is correct |
8 |
Correct |
388 ms |
117752 KB |
Output is correct |
9 |
Correct |
376 ms |
117732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
30076 KB |
Output is correct |
2 |
Correct |
503 ms |
107960 KB |
Output is correct |
3 |
Correct |
359 ms |
108212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
30076 KB |
Output is correct |
2 |
Correct |
503 ms |
107960 KB |
Output is correct |
3 |
Correct |
359 ms |
108212 KB |
Output is correct |
4 |
Correct |
22 ms |
29904 KB |
Output is correct |
5 |
Correct |
564 ms |
107748 KB |
Output is correct |
6 |
Correct |
425 ms |
107776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
29904 KB |
Output is correct |
2 |
Correct |
377 ms |
118564 KB |
Output is correct |
3 |
Correct |
361 ms |
118524 KB |
Output is correct |
4 |
Correct |
319 ms |
118524 KB |
Output is correct |
5 |
Correct |
21 ms |
29900 KB |
Output is correct |
6 |
Correct |
528 ms |
108028 KB |
Output is correct |
7 |
Correct |
401 ms |
108028 KB |
Output is correct |
8 |
Correct |
397 ms |
107676 KB |
Output is correct |
9 |
Correct |
437 ms |
107772 KB |
Output is correct |
10 |
Correct |
389 ms |
111868 KB |
Output is correct |
11 |
Correct |
418 ms |
111128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
29904 KB |
Output is correct |
2 |
Correct |
377 ms |
118564 KB |
Output is correct |
3 |
Correct |
361 ms |
118524 KB |
Output is correct |
4 |
Correct |
319 ms |
118524 KB |
Output is correct |
5 |
Correct |
21 ms |
29900 KB |
Output is correct |
6 |
Correct |
528 ms |
108028 KB |
Output is correct |
7 |
Correct |
401 ms |
108028 KB |
Output is correct |
8 |
Correct |
397 ms |
107676 KB |
Output is correct |
9 |
Correct |
437 ms |
107772 KB |
Output is correct |
10 |
Correct |
389 ms |
111868 KB |
Output is correct |
11 |
Correct |
418 ms |
111128 KB |
Output is correct |
12 |
Correct |
27 ms |
29892 KB |
Output is correct |
13 |
Correct |
439 ms |
118448 KB |
Output is correct |
14 |
Correct |
334 ms |
118356 KB |
Output is correct |
15 |
Correct |
427 ms |
117752 KB |
Output is correct |
16 |
Correct |
488 ms |
117688 KB |
Output is correct |
17 |
Correct |
22 ms |
29900 KB |
Output is correct |
18 |
Correct |
582 ms |
107776 KB |
Output is correct |
19 |
Correct |
487 ms |
107768 KB |
Output is correct |
20 |
Correct |
488 ms |
107256 KB |
Output is correct |
21 |
Correct |
478 ms |
107260 KB |
Output is correct |
22 |
Correct |
464 ms |
110144 KB |
Output is correct |
23 |
Correct |
488 ms |
111868 KB |
Output is correct |
24 |
Correct |
394 ms |
112124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
29904 KB |
Output is correct |
2 |
Correct |
40 ms |
34840 KB |
Output is correct |
3 |
Correct |
37 ms |
34800 KB |
Output is correct |
4 |
Correct |
35 ms |
34936 KB |
Output is correct |
5 |
Correct |
36 ms |
33028 KB |
Output is correct |
6 |
Correct |
34 ms |
34792 KB |
Output is correct |
7 |
Correct |
22 ms |
29908 KB |
Output is correct |
8 |
Correct |
413 ms |
105968 KB |
Output is correct |
9 |
Correct |
358 ms |
105724 KB |
Output is correct |
10 |
Correct |
24 ms |
29904 KB |
Output is correct |
11 |
Correct |
352 ms |
118524 KB |
Output is correct |
12 |
Correct |
349 ms |
118424 KB |
Output is correct |
13 |
Correct |
315 ms |
118528 KB |
Output is correct |
14 |
Correct |
23 ms |
29868 KB |
Output is correct |
15 |
Correct |
470 ms |
108060 KB |
Output is correct |
16 |
Correct |
416 ms |
108248 KB |
Output is correct |
17 |
Correct |
396 ms |
107772 KB |
Output is correct |
18 |
Correct |
406 ms |
107788 KB |
Output is correct |
19 |
Correct |
385 ms |
111784 KB |
Output is correct |
20 |
Correct |
422 ms |
111096 KB |
Output is correct |
21 |
Correct |
373 ms |
106492 KB |
Output is correct |
22 |
Correct |
409 ms |
106488 KB |
Output is correct |
23 |
Correct |
486 ms |
107004 KB |
Output is correct |
24 |
Correct |
472 ms |
106948 KB |
Output is correct |
25 |
Correct |
403 ms |
110584 KB |
Output is correct |
26 |
Correct |
358 ms |
108244 KB |
Output is correct |
27 |
Correct |
348 ms |
108288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
29904 KB |
Output is correct |
2 |
Correct |
40 ms |
34840 KB |
Output is correct |
3 |
Correct |
37 ms |
34800 KB |
Output is correct |
4 |
Correct |
35 ms |
34936 KB |
Output is correct |
5 |
Correct |
36 ms |
33028 KB |
Output is correct |
6 |
Correct |
34 ms |
34792 KB |
Output is correct |
7 |
Correct |
22 ms |
29908 KB |
Output is correct |
8 |
Correct |
413 ms |
105968 KB |
Output is correct |
9 |
Correct |
358 ms |
105724 KB |
Output is correct |
10 |
Correct |
24 ms |
29904 KB |
Output is correct |
11 |
Correct |
352 ms |
118524 KB |
Output is correct |
12 |
Correct |
349 ms |
118424 KB |
Output is correct |
13 |
Correct |
315 ms |
118528 KB |
Output is correct |
14 |
Correct |
23 ms |
29868 KB |
Output is correct |
15 |
Correct |
470 ms |
108060 KB |
Output is correct |
16 |
Correct |
416 ms |
108248 KB |
Output is correct |
17 |
Correct |
396 ms |
107772 KB |
Output is correct |
18 |
Correct |
406 ms |
107788 KB |
Output is correct |
19 |
Correct |
385 ms |
111784 KB |
Output is correct |
20 |
Correct |
422 ms |
111096 KB |
Output is correct |
21 |
Correct |
373 ms |
106492 KB |
Output is correct |
22 |
Correct |
409 ms |
106488 KB |
Output is correct |
23 |
Correct |
486 ms |
107004 KB |
Output is correct |
24 |
Correct |
472 ms |
106948 KB |
Output is correct |
25 |
Correct |
403 ms |
110584 KB |
Output is correct |
26 |
Correct |
358 ms |
108244 KB |
Output is correct |
27 |
Correct |
348 ms |
108288 KB |
Output is correct |
28 |
Correct |
27 ms |
29892 KB |
Output is correct |
29 |
Correct |
49 ms |
34512 KB |
Output is correct |
30 |
Correct |
45 ms |
34548 KB |
Output is correct |
31 |
Correct |
52 ms |
34512 KB |
Output is correct |
32 |
Correct |
43 ms |
32692 KB |
Output is correct |
33 |
Correct |
46 ms |
34576 KB |
Output is correct |
34 |
Correct |
23 ms |
29892 KB |
Output is correct |
35 |
Correct |
335 ms |
105716 KB |
Output is correct |
36 |
Correct |
372 ms |
105280 KB |
Output is correct |
37 |
Correct |
332 ms |
105148 KB |
Output is correct |
38 |
Correct |
24 ms |
29988 KB |
Output is correct |
39 |
Correct |
372 ms |
118012 KB |
Output is correct |
40 |
Correct |
327 ms |
118180 KB |
Output is correct |
41 |
Correct |
395 ms |
117756 KB |
Output is correct |
42 |
Correct |
400 ms |
117756 KB |
Output is correct |
43 |
Correct |
24 ms |
29900 KB |
Output is correct |
44 |
Correct |
544 ms |
107772 KB |
Output is correct |
45 |
Correct |
440 ms |
107768 KB |
Output is correct |
46 |
Correct |
488 ms |
107260 KB |
Output is correct |
47 |
Correct |
438 ms |
107264 KB |
Output is correct |
48 |
Correct |
489 ms |
110336 KB |
Output is correct |
49 |
Correct |
448 ms |
111864 KB |
Output is correct |
50 |
Correct |
398 ms |
112124 KB |
Output is correct |
51 |
Correct |
436 ms |
106236 KB |
Output is correct |
52 |
Correct |
480 ms |
106176 KB |
Output is correct |
53 |
Correct |
432 ms |
105560 KB |
Output is correct |
54 |
Correct |
427 ms |
106280 KB |
Output is correct |
55 |
Correct |
419 ms |
105976 KB |
Output is correct |
56 |
Correct |
429 ms |
106748 KB |
Output is correct |
57 |
Correct |
363 ms |
109748 KB |
Output is correct |
58 |
Correct |
517 ms |
107668 KB |
Output is correct |
59 |
Correct |
364 ms |
108280 KB |
Output is correct |