#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 3000
#define MD 0x7fffffff
int ppx[N + 1], ppy[N + 1], X, Y, Z;
void init() {
int i;
X = 12345, Y = 54321, Z = 76543;
ppx[0] = ppy[0] = 1;
for (i = 1; i <= N; i++) {
ppx[i] = (long long) ppx[i - 1] * X % MD;
ppy[i] = (long long) ppy[i - 1] * Y % MD;
}
}
int *ej[N], eo[N];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
char cc[N + 1];
char used[N]; int sz[N], c;
void dfs0(int p, int i, int n) {
int o, centroid;
sz[i] = 1, centroid = 1;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p && !used[j]) {
dfs0(i, j, n);
sz[i] += sz[j];
if (sz[j] * 2 > n)
centroid = 0;
}
}
if ((n - sz[i]) * 2 > n)
centroid = 0;
if (centroid)
c = i;
}
int oo[1 + N], kk1[1 + N], kk2[1 + N], kk3[1 + N], ht[N], _;
int hash(int k1, int k2, int k3) {
return (((long long) k1 * Z + k2) % MD * Z + k3) % MD % N;
}
void add(int k1, int k2, int k3) {
int h = hash(k1, k2, k3), o;
for (o = ht[h]; o; o = oo[o])
if (kk1[o] == k1 && kk2[o] == k2 && kk3[o] == k3)
return;
o = _++;
kk1[o] = k1, kk2[o] = k2, kk3[o] = k3;
oo[o] = ht[h], ht[h] = o;
}
int contains(int k1, int k2, int k3) {
int h = hash(k1, k2, k3), o;
for (o = ht[h]; o; o = oo[o])
if (kk1[o] == k1 && kk2[o] == k2 && kk3[o] == k3)
return 1;
return 0;
}
int dfs1(int p, int i, int d, int x1, int y1, int x2, int y2, int len) {
int o, a, x, y;
a = cc[i] - 'a';
x1 = ((long long) x1 * X + a) % MD, y1 = ((long long) y1 * Y + a) % MD;
x2 = (x2 + (long long) a * ppx[d]) % MD, y2 = (y2 + (long long) a * ppy[d]) % MD;
if (++d > len)
return 0;
x = (x1 - (long long) x2 * ppx[len - d]) % MD, y = (y1 - (long long) y2 * ppy[len - d]) % MD;
if (x < 0)
x += MD;
if (y < 0)
y += MD;
if (contains(x, y, len - d))
return 1;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p && !used[j] && dfs1(i, j, d, x1, y1, x2, y2, len))
return 1;
}
return 0;
}
int dfs2(int p, int i, int d, int x1, int y1, int x2, int y2, int len) {
int o, a, x, y;
a = cc[i] - 'a';
x1 = ((long long) x1 * X + a) % MD, y1 = ((long long) y1 * Y + a) % MD;
x2 = (x2 + (long long) a * ppx[d]) % MD, y2 = (y2 + (long long) a * ppy[d]) % MD;
if (++d > len)
return 0;
if (d == len && x1 == x2 && y1 == y2)
return 1;
x = (x1 - (long long) x2 * ppx[len - d]) % MD, y = (y1 - (long long) y2 * ppy[len - d]) % MD;
if (x < 0)
x += MD;
if (y < 0)
y += MD;
add(x, y, d);
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p && !used[j] && dfs2(i, j, d, x1, y1, x2, y2, len))
return 1;
}
return 0;
}
int cd(int i, int n, int len) {
int o;
dfs0(-1, i, n), used[i = c] = 1;
_ = 1;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (!used[j] && (dfs1(i, j, 0, 0, 0, 0, 0, len) || dfs2(i, j, 1, cc[i] - 'a', cc[i] - 'a', cc[i] - 'a', cc[i] - 'a', len)))
return 1;
}
while (--_)
ht[hash(kk1[_], kk2[_], kk3[_])] = 0;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (!used[j] && cd(j, sz[j] < sz[i] ? sz[j] : n - sz[i], len))
return 1;
}
return 0;
}
int solve(int n, int len) {
if (len == 1)
return 1;
if (len > n)
return 0;
memset(ht, 0, N * sizeof *ht);
memset(used, 0, n * sizeof *used);
return cd(0, n, len);
}
int main() {
int n, h, i, j, lower, upper;
init();
scanf("%d%s", &n, cc);
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (h = 0; h < n - 1; h++) {
scanf("%d%d", &i, &j), i--, j--;
append(i, j), append(j, i);
}
lower = 1, upper = (n + 1) / 2 + 1;
while (upper - lower > 1) {
int r = (lower + upper) / 2;
if (solve(n, r * 2 - 1) || solve(n, r * 2))
lower = r;
else
upper = r;
}
printf("%d\n", solve(n, lower * 2) ? lower * 2 : lower * 2 - 1);
return 0;
}
Compilation message
lampice.c: In function 'append':
lampice.c:26:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
26 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
lampice.c: In function 'main':
lampice.c:165:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | scanf("%d%s", &n, cc);
| ^~~~~~~~~~~~~~~~~~~~~
lampice.c:169:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
169 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
332 KB |
Output is correct |
| 2 |
Correct |
6 ms |
332 KB |
Output is correct |
| 3 |
Correct |
24 ms |
460 KB |
Output is correct |
| 4 |
Correct |
31 ms |
460 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
332 KB |
Output is correct |
| 7 |
Correct |
0 ms |
304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
972 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
972 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
332 KB |
Output is correct |
| 2 |
Correct |
6 ms |
332 KB |
Output is correct |
| 3 |
Correct |
24 ms |
460 KB |
Output is correct |
| 4 |
Correct |
31 ms |
460 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
332 KB |
Output is correct |
| 7 |
Correct |
0 ms |
304 KB |
Output is correct |
| 8 |
Runtime error |
1 ms |
972 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
