Submission #481334

#	Time	Username	Problem	Language	Result	Execution time	Memory
481334		rainboy	Lampice (COCI19_lampice)	C11	17 / 110	17 ms	2864 KiB

lampice

#include <stdio.h>
#include <stdlib.h>

#define N	50000

int abs_(int a) { return a > 0 ? a : -a; }
int max(int a, int b) { return a > b ? a : b; }

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]; int d_;

void dfs(int p1, int i1, int p2, int i2, int d) {
	int o1, o2;

	d_ = max(d_, d);
	for (o1 = eo[i1]; o1--; ) {
		int j1 = ej[i1][o1];

		for (o2 = eo[i2]; o2--; ) {
			int j2 = ej[i2][o2];

			if (j1 != p1 && j2 != p2 && (i1 != i2 || j1 < j2) && cc[j1] == cc[j2])
				dfs(i1, j1, i2, j2, d + 2);
		}
	}
}

int manacher(char *cc, int n) {
	static char cc_[N * 2 + 2];
	static int rr[N * 2 + 1];
	int i, o, x, ans;

	for (i = 0; i < n * 2 + 1; i++)
		cc_[i] = i % 2 == 0 ? ' ' : cc[i / 2];
	for (i = 1, o = 0, x = 0; i < n * 2 + 1; i++)
		if (i < x && i + rr[o + o - i] < x)
			rr[i] = rr[o + o - i];
		else {
			o = i, x = max(x, i);
			while (x < n * 2 + 1 && o + o - x >= 0 && cc[x] == cc[o + o - x])
				x++;
			rr[i] = x - o;
		}
	ans = 0;
	for (i = 0; i < n * 2 + 1; i++)
		ans = max(ans, rr[i]);
	return ans;
}

int main() {
	static int ii[N - 1], jj[N - 1];
	int n, h, i, j, line;

	scanf("%d%s", &n, cc);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	line = 1;
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		if (abs_(j - i) != 1)
			line = 0;
		ii[h] = i, jj[h] = j;
		append(i, j), append(j, i);
	}
	if (n <= 3000) {
		for (i = 0; i < n; i++)
			dfs(-1, i, -1, i, 1);
		for (h = 0; h < n - 1; h++)
			if (cc[ii[h]] == cc[jj[h]])
				dfs(ii[h], jj[h], jj[h], ii[h], 2);
	} else if (line)
		d_ = manacher(cc, n);
	printf("%d\n", d_);
	return 0;
}

Compilation message (stderr)

lampice.c: In function 'append':
lampice.c:14:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
lampice.c: In function 'manacher':
lampice.c:38:14: warning: variable 'cc_' set but not used [-Wunused-but-set-variable]
   38 |  static char cc_[N * 2 + 2];
      |              ^~~
lampice.c: In function 'main':
lampice.c:63:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%d%s", &n, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~
lampice.c:68:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

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