제출 #545129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545129		rainboy	Sailing Race (CEOI12_race)	C11	100 / 100	1183 ms	5328 KiB

race

#include <stdio.h>
#include <string.h>
 
#define N	500
#define add(x) (x + 1 == n ? 0 : x + 1)
#define sub(x) (x == 0 ? n - 1 : x - 1)
 
int max(int a, int b) { return a > b ? a : b; }
 
int main() {
	static int aa[N][N], dp[N][N], dq[N][N], dr[N][N], ds[N][N], dt[N];
	int n, t, i, i_, j, k, l, x_;
 
	scanf("%d%d", &n, &t);
	for (i = 0; i < n; i++)
		while (1) {
			scanf("%d", &j), j--;
			if (j == -1)
				break;
			aa[i][j] = 1;
		}
	for (i = 0; i < n; i++) {
		memset(dp[i], -1, n * sizeof *dp[i]);
		dp[i][i] = 0;
		j = i;
		do {
			int x = dp[i][j];
 
			if (x != -1)
				for (k = add(j); k != i; k = add(k))
					if (aa[j][k])
						dp[i][k] = max(dp[i][k], x + 1);
			j = add(j);
		} while (j != i);
		memset(dq[i], -1, n * sizeof *dq[i]);
		dq[i][i] = 0;
		j = i;
		do {
			int x = dq[i][j];
 
			if (x != -1)
				for (k = sub(j); k != i; k = sub(k))
					if (aa[j][k])
						dq[i][k] = max(dq[i][k], x + 1);
			j = sub(j);
		} while (j != i);
	}
	for (l = 1; l < n; l++)
		for (i = 0; i < n; i++) {
			int x;
 
			j = (i + l) % n;
			x = -1, k = add(i);
			while (1) {
				if (aa[i][k])
					x = max(x, max(ds[add(i)][k], dr[j][k]));
				if (k == j)
					break;
				k = add(k);
			}
			dr[j][i] = x + 1;
			x = -1, k = sub(j);
			while (1) {
				if (aa[j][k])
					x = max(x, max(dr[sub(j)][k], ds[i][k]));
				if (k == i)
					break;
				k = sub(k);
			}
			ds[i][j] = x + 1;
		}
	x_ = 0, i_ = 0;
	for (i = 0; i < n; i++) {
		int x = dr[(i - 1 + n) % n][i];
 
		if (x_ < x)
			x_ = x, i_ = i;
	}
	if (t == 1)
		for (j = 0; j < n; j++) {
			memset(dt, -1, n * sizeof *dt);
			for (i = add(j); i != j; i = add(i)) {
				if (aa[i][j])
					for (k = add(i); k != j; k = add(k))
						if (dt[k] != -1) {
							int x = 1 + dt[k] + max(dr[sub(j)][k], ds[add(i)][k]);
 
							if (x_ < x)
								x_ = x, i_ = i;
						}
				if (dp[j][i] != -1)
					for (k = add(i); k != j; k = add(k))
						if (aa[i][k])
							dt[k] = max(dt[k], dp[j][i] + 1);
			}
			memset(dt, -1, n * sizeof *dt);
			for (i = sub(j); i != j; i = sub(i)) {
				if (aa[i][j])
					for (k = sub(i); k != j; k = sub(k))
						if (dt[k] != -1) {
							int x = 1 + dt[k] + max(ds[add(j)][k], dr[sub(i)][k]);
 
							if (x_ < x)
								x_ = x, i_ = i;
						}
				if (dq[j][i] != -1)
					for (k = sub(i); k != j; k = sub(k))
						if (aa[i][k])
							dt[k] = max(dt[k], dq[j][i] + 1);
			}
		}
	printf("%d\n", x_);
	printf("%d\n", i_ + 1);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

race.c: In function 'main':
race.c:14:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d%d", &n, &t);
      |  ^~~~~~~~~~~~~~~~~~~~~
race.c:17:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |    scanf("%d", &j), j--;
      |    ^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100