oj.uz

답안 #481340

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
481340 2021-10-20T12:24:14 Z rainboy Lampice (COCI19_lampice) C
42 / 110
 37 ms 7888 KB 
#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 dfs1(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])
				dfs1(i1, j1, i2, j2, d + 2);
		}
	}
}

int pp[N], dd[N];

void dfs2(int p, int i, int d) {
	int o;

	pp[i] = p, dd[i] = d;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs2(i, j, d + 1);
	}
}

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 = 0, 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] - 1);
	return ans;
}

int main() {
	static int ii[N - 1], jj[N - 1], qu[N], qu1[N], qu2[N];
	static char cc_[N + 1];
	int n, h, h_, i, j, cnt, cnt1, cnt2;

	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--;
		ii[h] = i, jj[h] = j;
		append(i, j), append(j, i);
	}
	if (n <= 3000) {
		for (i = 0; i < n; i++)
			dfs1(-1, i, -1, i, 1);
		for (h = 0; h < n - 1; h++)
			if (cc[ii[h]] == cc[jj[h]])
				dfs1(ii[h], jj[h], jj[h], ii[h], 2);
	} else {
		dfs2(-1, 0, 0);
		cnt = 0;
		for (i = 0; i < n; i++)
			if (eo[i] == 1)
				qu[cnt++] = i;
		for (h = 0; h < cnt; h++)
			for (h_ = h + 1; h_ < cnt; h_++) {
				i = qu[h], j = qu[h_];
				cnt1 = 0, cnt2 = 0;
				while (i != j)
					if (dd[i] > dd[j])
						qu1[cnt1++] = i, i = pp[i];
					else
						qu2[cnt2++] = j, j = pp[j];
				for (h = 0; h < cnt1; h++)
					cc_[h] = cc[qu1[h]];
				cc_[cnt1] = cc[i];
				for (h = 0; h < cnt2; h++)
					cc_[cnt1 + cnt2 - h] = cc[qu2[h]];
				d_ = max(d_, manacher(cc_, cnt1 + 1 + cnt2));
			}
	}
	printf("%d\n", d_);
	return 0;
}

Compilation message

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 'main':
lampice.c:78:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  scanf("%d%s", &n, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~
lampice.c:82:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 6936 KB Output is correct
2 Correct 16 ms 6988 KB Output is correct
3 Correct 17 ms 7212 KB Output is correct
4 Correct 18 ms 7488 KB Output is correct
5 Correct 23 ms 7888 KB Output is correct
6 Correct 25 ms 7884 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 4468 KB Output is correct
2 Correct 29 ms 4172 KB Output is correct
3 Correct 34 ms 4380 KB Output is correct
4 Incorrect 31 ms 4452 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 17 ms 6936 KB Output is correct
9 Correct 16 ms 6988 KB Output is correct
10 Correct 17 ms 7212 KB Output is correct
11 Correct 18 ms 7488 KB Output is correct
12 Correct 23 ms 7888 KB Output is correct
13 Correct 25 ms 7884 KB Output is correct
14 Correct 37 ms 4468 KB Output is correct
15 Correct 29 ms 4172 KB Output is correct
16 Correct 34 ms 4380 KB Output is correct
17 Incorrect 31 ms 4452 KB Output isn't correct
18 Halted 0 ms 0 KB -