Submission #1158481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158481		sleepntsheep	Lampice (COCI19_lampice)	C++20	73 / 110	5094 ms	326656 KiB

lampice

#pragma GCC optimize("O3,unroll-loops")

#include <stdio.h>
#include <string.h>

#define N (50005)
#define M 1000000007

#define fprintf(...) 42
#define EVEN 0x1
#define ODD 0x3

int dead[N], Base = 137, n, *eh[N], eo[N], Z[N + N], Z_, sz[N], answer = 1, mode, len, t1[N], t2[N], bp[1 + N], bpi[1 + N], ii, sentinel;
unsigned seed;

char s[N];

int bpow(int a, int b) {
	if (!b) return 1;
	int r = bpow(a, b / 2);
	if (b & 1) return r * 1ll * r % M * a % M;
	return r * 1ll * r %M;
}

int *rizz(int n) {
	return Z + (Z_ += n) - n;
}

void init() {
	bp[0] = 1;
	for (int i = 1; i <= N; ++i)
		bp[i] = bp[i - 1] * 1ll * Base % M;
	for (int i = 0; i <= N; ++i)
		bpi[i] = bpow(bp[i], M - 2);

	static int u[N], v[N];
	scanf("%d%s", &n, s + 1);

	for (int i = 1; i < n; ++i) {
		scanf("%d%d", &u[i], &v[i]);
		++eo[u[i]]; ++eo[v[i]];
	}

	for (int i = 1; i <= n; ++i) {
		eh[i] = rizz(eo[i]);
		eo[i] = 0;
	}

	for (int i = 1; i < n; ++i) {
		eh[u[i]][eo[u[i]]++] = v[i];
		eh[v[i]][eo[v[i]]++] = u[i];
	}
}

void dfs(int u, int p) {
	sz[u] = 1;
	for (int *v = eh[u]; eh[u] + eo[u] > v; ++v)
		if (! dead[*v] && *v != p)
			dfs(*v, u), sz[u] += sz[*v];
}

int get_centroid(int u, int p, int tsz) {
	for (int *v = eh[u]; eh[u] + eo[u] > v; ++v)
		if (! dead[*v] && *v != p && 2 * sz[*v] >= tsz)
			return get_centroid(*v, u, tsz);
	return u;
}

void centroid_reset() {
	memset(dead, 0, sizeof dead);
	ii = 0;
}

typedef unsigned Hash[31999999];

int has;
Hash mset, mset_short, mset_equal;

void mset_insert(Hash *v, int k) {
	v[0][k >> 5] |= 1 << (k & 31);
}

void mset_unset(Hash *v, int k) {
	v[0][k >> 5] = 0;
}

int mset_count(Hash *v, int k) {
	return (v[0][k >> 5] >> (k & 31)) & 1;
}

void upd(int *t, int p, int k) {
	t[p] = (t[p - 1] + k) % M;
}

int qry(int *t, int l, int r) {
	if (l)
		return (t[r] + (M - t[l - 1]) % M) % M;
	return t[r];
}

void efs(int u, int p, int update, int dep) {
	if (dep >= len)
		return;

	upd(t1, dep, (s[u] - 'Z' ) * 1ll * bp[dep] % M);
	upd(t2, dep, (s[u] - 'Z' ) * 1ll * bp[N - dep] % M);

	int y = len - dep;
	int x = (dep - y) / 2;

	if (mode == EVEN) {
		if (update) {
			if (dep * 2 < len) {
				mset_insert(&mset_short, qry(t1, 0, dep));
			} else {
				int y = len - dep;
				int x = (dep - y) / 2;

				if (x > 0 && qry(t1, 1, x) * 1ll * bpi[1] % M 
						!= qry(t2, x + 1, 2 * x) * 1ll *  bpi[N - 2 * x] % M) {
				}
				else if (y > 1) {
					mset_insert(&mset, qry(t1, 2 * x + 1, dep) * 1ll * bpi[2 * x + 1] % M);
				}
				else if ((s[u] - 'Z') == qry(t1, 0, 0))
					++has;
			}
		} else {
			if (dep * 2 < len) {
					has += mset_count(&mset, qry(t1, 0, dep));
			} else {
				int y = len - dep;
				int x = (dep - y) / 2;

				if (qry(t1, 1, x) * 1ll * bpi[1] % M 
						!= qry(t2, x + 1, 2 * x) * 1ll *  bpi[N - 2 * x] % M) {

				} else if (y > 1) {
					has += mset_count(&mset_short, qry(t1, 2 * x + 1, dep) * 1ll * bpi[2 * x + 1] % M);
				}
			}
		}
	} else if (mode == ODD) {
		if (update) {
			if (dep * 2 + 1 == len) {
				mset_insert(&mset_equal, qry(t1, 0, dep));
			} else if (dep * 2 < len) {
				mset_insert(&mset_short, qry(t1, 0, dep));
			} else {

				if (x > 0 && qry(t1, 1, x) * 1ll * bpi[1] % M 
						!= qry(t2, x + 2, x + 2 + x - 1) * 1ll * bpi[N - 2 * x - 1] % M) {
				}
				else if (y > 1) {
					mset_insert(&mset, qry(t1, 2 * x + 2, dep) * 1ll * bpi[2 * x + 2] % M);
				}
				else
					if (s[u] - 'Z' == qry(t1, 0, 0)) {
						++has;
					}
			}
		} else {
			if (dep * 2 + 1 == len) {
				has += mset_count(&mset_equal, qry(t1, 0, dep));
			} else if (dep * 2 < len) {
				has += mset_count(&mset, qry(t1, 0, dep));
			} else {
				if (qry(t1, 1, x) * 1ll * bpi[1] % M 
						!= qry(t2, x + 2, x + 2 + x - 1) * 1ll *  bpi[N - 2 * x - 1] % M) {
				}
				else if (y > 1) {
					has += mset_count(&mset_short, qry(t1, 2 * x + 2, dep) * 1ll * bpi[2 * x + 2] % M);
				}
			}
		}
	}


	for (int *v = eh[u]; eh[u] + eo[u] > v; ++v)
		if (! dead[*v] && *v != p)
			efs(*v, u, update, dep + 1);
}

void efs_clear(int u, int p, int dep) {
	if (dep >= len)
		return;

	int y = len - dep;
	int x = (dep - y) / 2;

	upd(t1, dep, (s[u] - 'Z' ) * 1ll * bp[dep] % M);
	upd(t2, dep, (s[u] - 'Z' ) * 1ll * bp[N - dep] % M);

	if (mode == EVEN) {
		if (dep * 2 < len)
			mset_unset(&mset_short, qry(t1, 0, dep));
		else
			mset_unset(&mset, qry(t1, 2 * x + 1, dep) * 1ll * bpi[2 * x + 1] % M);
	} else if (mode == ODD) {
		if (dep * 2 + 1 == len)
			mset_unset(&mset_equal, qry(t1, 0, dep));
		else if (dep * 2 < len)
			mset_unset(&mset_short, qry(t1, 0, dep));
		else
			mset_unset(&mset, qry(t1, 2 * x + 2, dep) * 1ll * bpi[2 * x + 2] % M);
	}

	for (int *v = eh[u]; eh[u] + eo[u] > v; ++v)
		if (! dead[*v] && *v != p)
			efs_clear(*v, u, dep + 1);
}


void centroid_decomposition(int u, int dep, int par) {
	dfs(u, u);
	u = get_centroid(u, u, sz[u]);
	dead[u] = 1;

	/* process */
	upd(t1, 0, s[u] - 'Z');
	upd(t2, 0, (s[u] - 'Z' ) * 1ll * bp[N - 0] % M);

	for (int *v = eh[u]; eh[u] + eo[u] > v; ++v) {
		efs(*v, 0, 0, 1);
		efs(*v, 0, 1, 1);
	}

	for (int *v = eh[u]; eh[u] + eo[u] > v; ++v)
		efs_clear(*v, 0, 1);

	/* decomp */
	for (int *v = eh[u]; eh[u] + eo[u] > v; ++v)
		if (! dead[*v])
			centroid_decomposition(*v, dep + 1, u);
}

void find_even() {
	mode = EVEN;

	int lower = 0, upper = n / 2 + 1;
	while (upper - lower > 1) {
		int mid = lower + (upper - lower) / 2;
		len = mid * 2;

		has = 0;
		centroid_reset();
		centroid_decomposition(1, 0, 0);

		if (has)
			lower = mid;
		else
			upper = mid;
	}
	if (answer < lower * 2)
		answer = lower * 2;
}

void find_odd() {
	mode = ODD;

	int lower = 1, upper = (n + 1) / 2 + 1;
	while (upper - lower > 1) {
		int mid = lower + (upper - lower) / 2;
		len = mid * 2 - 1;

		has = 0;
		if (len <= answer)
			has = 1;
		else {
			centroid_reset();
			centroid_decomposition(1, 0, 0);
		}

		if (has)
			lower = mid;
		else
			upper = mid;
	}

	if (answer < lower * 2 - 1)
		answer = lower * 2 - 1;
}

int main() {
	init();
	find_even();
	find_odd();

	printf("%d\n", answer);

	return 0;
}

Compilation message (stderr)

lampice.cpp: In function 'void init()':
lampice.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d%s", &n, s + 1);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
lampice.cpp:40:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |                 scanf("%d%d", &u[i], &v[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 31 / 31
• Subtask 4: 0 / 37