Submission #481387

#	Time	Username	Problem	Language	Result	Execution time	Memory
481387		rainboy	Lampice (COCI19_lampice)	C11	110 / 110	2419 ms	8996 KiB

lampice

#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 (stderr)

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 / 17
• Subtask 2: 25 / 25
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37