#include <stdio.h>
#include <stdlib.h>
int max(int i, int j) { return i > j ? i : j; }
/*
* For "Q" queries, use LCA + prefix sum on tree ~ 3O(lgn) [for finding lca and almost-lca]
*
* Every B queries of any type, do naive dp on tree (reverse edge order)
* to find answer for "C" queries ~ O(n)
*
* On "C" queries, use cached answer from above and count all edges that appeared after that (by "Q")
* ~ O(B lgn)
*
*
* Time complexity = O(N^2 / B) + O(N lgn) + O(N B lgn)
*
* Let B = sqrt(N / lgN)
*
* Should be able to optimize to O(N^1.5) using https://codeforces.com/blog/entry/71567?mobile=true&locale=en
*/
#define N 120001
#define B 200
int n, q, pp[N], dd[N], up[N], temp, inc[N], tin[N], timer, hld[N], ds[N], sz[N], dp[N], counted[N];
int ds_find(int i) { return ds[i] == i ? i : (ds[i] = ds_find(ds[i])); }
void pus_(int **eh, int *eo, int i, int j) {
int o = eo[i]++;
if (0 == o) eh[i] = (int*)malloc(2 * sizeof **eh);
else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
eh[i][o] = j;
}
int *eh[N], *fh[N], eo[N];
void link(int u, int v, int w) {
pus_(eh, eo, u, v);
--eo[u];
pus_(fh, eo, u, w);
pus_(eh, eo, v, u);
--eo[v];
pus_(fh, eo, v, w);
}
void dfs(int u, int p) {
sz[u] = 1;
inc[u] = (up[u] > up[p]) + inc[p];
for (int j = 0; j < eo[u]; ++j) if (eh[u][j] != p) {
int v = eh[u][j];
dd[v] = dd[u] + 1;
pp[v] = u;
up[v] = fh[u][j];
dfs(v, u);
sz[u] += sz[v];
}
for (int j = 0; j < eo[u]; ++j) if (eh[u][j] == p) { /* remove parent from adj */
int ww = fh[u][j];
for (int k = j + 1; k < eo[u]; ++k)
eh[u][k - 1] = eh[u][k], fh[u][k - 1] = fh[u][k];
--eo[u];
break;
}
for (int j = 0; j < eo[u]; ++j) { /* hld prep */
int v = eh[u][j];
if (sz[v] > sz[eh[u][0]]) {
temp = eh[u][0], eh[u][0] = v, eh[u][j] = temp;
temp = fh[u][0], fh[u][0] = fh[u][j], fh[u][j] = temp;
}
}
}
void efs(int u, int hd) {
tin[u] = timer++;
hld[u] = hd;
for (int j = 0; j < eo[u]; ++j)
efs(eh[u][j], j ? eh[u][j] : hd);
}
int lca(int u, int v) {
while (hld[u] != hld[v])
if (dd[hld[u]] >= dd[hld[v]]) u = pp[hld[u]];
else v = pp[hld[v]];
return dd[u] <= dd[v] ? u : v;
}
struct Query {
char type[2];
int a, b;
} qq[N * 2];
int navigate(int u, int v) {
int lb = -1, ub = eo[u];
while (ub-lb>1){
int md=lb+(ub-lb)/2;
if(tin[eh[u][md]]<=tin[v])lb=md;
else ub=md;
}
return eh[u][lb];
}
/* u = data node, v = ask node */
int query_yesno(int u, int v, int time) {
if (u == v) return 1;
int a = lca(u, v), va, ua;
va = navigate(a, v);
ua = navigate(a, u);
if (u == a)
return inc[v] - inc[va] == dd[v] - dd[va] && up[v] <= time;
if (v == a)
return inc[u] - inc[ua] == 0 && up[ua] <= time;
return (dd[v] - dd[va] == inc[v] - inc[va]) && (inc[u] - inc[ua] == 0)
&& up[va] > up[ua] && up[v] <= time;
}
void build(int ii, int tme) {
for (int i = 1; i <= n; ++i) dp[i] = 1, ds_find(i);
for (int i = ii; i >= 0; --i)
if (qq[i].type[0] == 'S') {
int x = dp[qq[i].a], y = dp[qq[i].b];
dp[qq[i].a] += y;
dp[qq[i].b] += x;
}
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++i) ds[i] = i;
q = n + q - 1;
for (int j = 0, i = 0, a, b; i < q; ++i) {
scanf(" %s%d", qq[i].type, &qq[i].a);
if (qq[i].type[0] == 'S') {
scanf("%d", &b);
link(qq[i].a, qq[i].b, j++);
} else if (qq[i].type[0] == 'Q')
scanf("%d", &qq[i].b);
}
up[1] = 1e9;
pp[1] = 1;
dfs(1, 1);
efs(1, 1);
build(-1, -1);
int at = 0;
for (int j = 0, i = 0; i < q; ++i) {
if (qq[i].type[0] == 'S')
++j;
if (i % B == 0) {
for (int k = at; k <= i; ++k)
if (qq[k].type[0] == 'S')
ds[ds_find(qq[k].a)] = qq[k].b;
build(i, j - 1);
at = i + 1;
}
if (qq[i].type[0] == 'Q')
puts(query_yesno(qq[i].b, qq[i].a, j - 1) ? "yes": "no");
else if (qq[i].type[0] == 'C') {
int addition = 0;
for (int k = at; k < i; ++k)
if (qq[k].type[0] == 'S') {
int a[2] = {qq[k].a, qq[k].b};
for (int ii = 0; ii < 2; ++ii)
if (counted[a[ii]] != i + 1 &&
ds_find(a[ii]) != ds_find(qq[i].a) && query_yesno(qq[i].a, a[ii], j - 1))
++addition, counted[a[ii]] = i + 1;
}
printf("%d\n", dp[qq[i].a] + addition);
}
}
}
Compilation message
servers.c: In function 'pus_':
servers.c:32:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
32 | else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
| ~~^~~
servers.c: In function 'dfs':
servers.c:60:9: warning: unused variable 'ww' [-Wunused-variable]
60 | int ww = fh[u][j];
| ^~
servers.c: In function 'main':
servers.c:136:26: warning: unused variable 'a' [-Wunused-variable]
136 | for (int j = 0, i = 0, a, b; i < q; ++i) {
| ^
servers.c:132:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | scanf("%d%d", &n, &q);
| ^~~~~~~~~~~~~~~~~~~~~
servers.c:137:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | scanf(" %s%d", qq[i].type, &qq[i].a);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
servers.c:139:7: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
139 | scanf("%d", &b);
| ^~~~~~~~~~~~~~~
servers.c:142:7: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | scanf("%d", &qq[i].b);
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
16468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
16468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
16476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
16476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3565 ms |
8540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3565 ms |
8540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3552 ms |
8540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3552 ms |
8540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3559 ms |
8540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3559 ms |
8540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
16468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
16468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
