oj.uz

답안 #481339

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
481339 2021-10-20T12:17:55 Z rainboy Lampice (COCI19_lampice) C
42 / 110
 20 ms 3276 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 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 = 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];
	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

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: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.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 20 ms 2916 KB Output is correct
2 Correct 14 ms 3024 KB Output is correct
3 Correct 13 ms 3020 KB Output is correct
4 Correct 14 ms 3224 KB Output is correct
5 Correct 17 ms 3276 KB Output is correct
6 Correct 14 ms 3268 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 2856 KB Output isn't correct
2 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 20 ms 2916 KB Output is correct
9 Correct 14 ms 3024 KB Output is correct
10 Correct 13 ms 3020 KB Output is correct
11 Correct 14 ms 3224 KB Output is correct
12 Correct 17 ms 3276 KB Output is correct
13 Correct 14 ms 3268 KB Output is correct
14 Incorrect 15 ms 2856 KB Output isn't correct
15 Halted 0 ms 0 KB -