oj.uz

Submission #481387

# Submission time Handle Problem Language Result Execution time Memory
481387 2021-10-20T15:58:42 Z rainboy Lampice (COCI19_lampice) C
110 / 110
 2419 ms 8996 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	50000
#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--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Output is correct
2 Correct 6 ms 944 KB Output is correct
3 Correct 24 ms 972 KB Output is correct
4 Correct 30 ms 972 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1062 ms 7928 KB Output is correct
2 Correct 893 ms 8152 KB Output is correct
3 Correct 1154 ms 8452 KB Output is correct
4 Correct 1223 ms 8676 KB Output is correct
5 Correct 1666 ms 8996 KB Output is correct
6 Correct 69 ms 8624 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1983 ms 5580 KB Output is correct
2 Correct 2419 ms 5192 KB Output is correct
3 Correct 1734 ms 5456 KB Output is correct
4 Correct 1812 ms 5316 KB Output is correct
5 Correct 1482 ms 5132 KB Output is correct
6 Correct 1398 ms 4940 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Output is correct
2 Correct 6 ms 944 KB Output is correct
3 Correct 24 ms 972 KB Output is correct
4 Correct 30 ms 972 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1062 ms 7928 KB Output is correct
9 Correct 893 ms 8152 KB Output is correct
10 Correct 1154 ms 8452 KB Output is correct
11 Correct 1223 ms 8676 KB Output is correct
12 Correct 1666 ms 8996 KB Output is correct
13 Correct 69 ms 8624 KB Output is correct
14 Correct 1983 ms 5580 KB Output is correct
15 Correct 2419 ms 5192 KB Output is correct
16 Correct 1734 ms 5456 KB Output is correct
17 Correct 1812 ms 5316 KB Output is correct
18 Correct 1482 ms 5132 KB Output is correct
19 Correct 1398 ms 4940 KB Output is correct
20 Correct 1169 ms 4044 KB Output is correct
21 Correct 1397 ms 4420 KB Output is correct
22 Correct 1823 ms 4488 KB Output is correct
23 Correct 508 ms 3984 KB Output is correct
24 Correct 2236 ms 5012 KB Output is correct
25 Correct 1575 ms 4744 KB Output is correct
26 Correct 1837 ms 5872 KB Output is correct
27 Correct 2025 ms 4784 KB Output is correct
28 Correct 1450 ms 4092 KB Output is correct
29 Correct 1436 ms 4164 KB Output is correct
30 Correct 1648 ms 5708 KB Output is correct
31 Correct 1804 ms 4456 KB Output is correct
32 Correct 1118 ms 6528 KB Output is correct
33 Correct 1028 ms 4676 KB Output is correct