#include <stdio.h>
#include <stdlib.h>
int max(int i, int j){ return i > j ? i : j; }
#define N 120001
int n, q, pp[N], jj[N], dd[N], up[N], temp, inc[N];
int *eh[N], *fh[N], eo[N];
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;
}
void link(int u, int v, int w) {
pus_(eh, eo, u, v);
--eo[u];
pus_(fh, eo, u, v);
pus_(eh, eo, v, u);
--eo[v];
pus_(fh, eo, v, u);
}
void dfs(int u, int p) {
dd[u] = dd[pp[u] = p] + 1;
jj[u] = (dd[jj[p]] - dd[jj[jj[p]]] == dd[p] - dd[jj[p]]) ? jj[jj[p]] : p;
inc[u] = (up[u] > up[p]) + inc[p];
for (int j = 0; j < eo[u]; ++j) if (eh[u][j] != p) {
up[eh[u][j]] = fh[u][j];
dfs(eh[u][j], u);
}
}
int lca(int u, int v) {
while (dd[u] != dd[v]) {
if (dd[u] < dd[v]) temp = u, u = v, v = temp;
u = (dd[jj[u]] >= dd[v]) ? jj[u] : pp[u];
}
while (u != v)
if (jj[u] != jj[v]) u = jj[u], v = jj[v];
else u = pp[u], v = pp[v];
return u;
}
int anc(int u, int dep) {
while (dd[u] > dep)
u = (dd[jj[u]] >= dep) ? jj[u] : pp[u];
return u;
}
struct Query {
char type;
int a, b;
int ans;
} qq[N];
/* v = ask node, u = data node */
int query_yesno(int u, int v, int time) {
if (u == v) return 1;
int a = lca(u, v);
int va = anc(v, dd[a] + 1);
int ua = anc(u, dd[a] + 1);
if (u == a) {
return inc[v] - inc[va] == dd[v] - dd[a] - 1 && up[v] <= time;
}
if (v == a)
return inc[u] - inc[ua] == 0 && up[ua] <= time;
return (dd[v] - dd[a] + 1 == inc[v] - inc[va]) && (0 == inc[u] - inc[ua])
&& up[va] < up[ua] && up[v] <= time;
}
int main() {
scanf("%d%d", &n, &q);
q = n + q - 1;
for (int j = 0, i = 0; i < q; ++i) {
char c;
int a, b;
scanf(" %c%d", &c, &a);
if (c == 'S') {
scanf("%d", &b);
link(a, b, j++);
} else if (c == 'Q') {
scanf("%d", &b);
} else {
}
qq[i] = (struct Query){c, a, b};
}
up[1] = 1e9;
pp[1] = 1;
jj[1] = 1;
dfs(1, 1);
for (int j = 0, i = 0; i < q; ++i) {
if (qq[i].type == 'S') ++j;
if (qq[i].type == 'Q') {
puts(query_yesno(qq[i].b, qq[i].a, j) ? "yes": "no");
}
}
}
Compilation message
servers.c: In function 'pus_':
servers.c:14:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
14 | else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
| ~~^~~
servers.c: In function 'main':
servers.c:79:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d%d", &n, &q);
| ^~~~~~~~~~~~~~~~~~~~~
servers.c:85:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf(" %c%d", &c, &a);
| ^~~~~~~~~~~~~~~~~~~~~~
servers.c:87:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d", &b);
| ^~~~~~~~~~~~~~~
servers.c:90:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | scanf("%d", &b);
| ^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3575 ms |
4188 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3575 ms |
4188 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3560 ms |
4188 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3560 ms |
4188 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
8280 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
8280 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3594 ms |
4184 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3594 ms |
4184 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
8280 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
8280 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3573 ms |
4188 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3573 ms |
4188 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
