#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100000
#define LN 17 /* LN = ceil(log2(N)) */
#define N_ (N * (LN + 4))
int len[N_], tt[N_][2], ff[N_], fff[N_][2];
int node(int l) {
static int _ = 1;
len[_] = l;
return _++;
}
int ds[N], ans[N], *aa[N], head[N], cnt[N], cnt_[N], ss0[N], ss1[N], pp[N], qq[N];
void append(int i, int a) {
int s;
if (cnt[i] == cnt_[i]) {
int *bb = (int *) malloc((cnt_[i] *= 2) * sizeof *bb), h;
for (h = 0; h < cnt[i]; h++)
bb[h] = aa[i][(head[i] + h) % cnt[i]];
free(aa[i]);
aa[i] = bb, head[i] = 0;
}
aa[i][(head[i] + cnt[i]++) % cnt_[i]] = a;
s = qq[i];
if (len[s] == cnt[i] - 1 || aa[i][(head[i] + cnt[i] - 2 - len[s]) % cnt_[i]] != a)
s = fff[s][a];
if (!tt[s][a]) {
int u = node(len[s] + 2), f = fff[s][a] == ss1[i] ? ss0[i] : tt[fff[s][a]][a];
ff[u] = f;
memcpy(fff[u], fff[f], sizeof fff[f]);
fff[u][aa[i][(head[i] + cnt[i] - 1 - len[f]) % cnt_[i]]] = f;
ans[i]++;
}
s = tt[s][a];
qq[i] = s;
if (len[s] == cnt[i])
pp[i] = s;
}
void prepend(int i, int a) {
int s;
if (cnt[i] == cnt_[i]) {
int *bb = (int *) malloc((cnt_[i] *= 2) * sizeof *bb), h;
for (h = 0; h < cnt[i]; h++)
bb[h] = aa[i][(head[i] + h) % cnt[i]];
free(aa[i]);
aa[i] = bb, head[i] = 0;
}
head[i] = (head[i] - 1 + cnt_[i]) % cnt_[i], cnt[i]++, aa[i][head[i]] = a;
s = pp[i];
if (len[s] == cnt[i] - 1 || aa[i][(head[i] + 1 + len[s]) % cnt_[i]] != a)
s = fff[s][a];
if (!tt[s][a]) {
int u = node(len[s] + 2), f = fff[s][a] == ss1[i] ? ss0[i] : tt[fff[s][a]][a];
ff[u] = f;
memcpy(fff[u], fff[f], sizeof fff[f]);
fff[u][aa[i][(head[i] + len[f]) % cnt_[i]]] = f;
ans[i]++;
}
s = tt[s][a];
pp[i] = s;
if (len[s] == cnt[i])
qq[i] = s;
}
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
void join(int i, int j) {
int h;
i = find(i);
j = find(j);
if (i == j)
return;
if (cnt[i] > cnt[j]) {
ds[j] = i;
for (h = 0; h < cnt[j]; h++)
append(i, aa[j][(head[j] + h) % cnt_[j]]);
free(aa[j]);
} else {
ds[i] = j;
for (h = cnt[i] - 1; h >= 0; h--)
prepend(j, aa[i][(head[i] + h) % cnt_[i]]);
free(aa[i]);
}
}
int main() {
static char cc[N + 1];
int n, h, i, j;
scanf("%d%s", &n, cc);
for (i = 0; i < n; i++) {
aa[i] = (int *) malloc((cnt_[i] = 2) * sizeof *aa[i]);
head[i] = 0;
ss0[i] = node(0), ss1[i] = node(-1);
ff[ss0[i]] = ss1[i], fff[ss0[i]][0] = fff[ss0[i]][1] = ss1[i];
pp[i] = qq[i] = ss0[i];
append(i, cc[i] - '0');
}
memset(ds, -1, n * sizeof *ds);
for (h = 0; h < n - 1; h++) {
scanf("%d%d", &i, &j), i--, j--;
join(i, j);
printf("%d\n", ans[find(i)]);
}
return 0;
}
Compilation message
Main.c: In function 'main':
Main.c:106:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d%s", &n, cc);
| ^~~~~~~~~~~~~~~~~~~~~
Main.c:117:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
14728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
