oj.uz

답안 #321467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321467 2020-11-12T12:19:27 Z MetB Sailing Race (CEOI12_race) C++14
5 / 100
 1364 ms 7404 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 2000000;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

int path[500][500][2], dp[500][500][2], dp_max[500][500][2];

int g[500][500], k;
int ans[500], n, m, nx[500][2];


void f_edge (int l, int r, int dir) {
	path[l][r][dir] = 1;
	dp[l][r][dir] = 1 + dp_max[r][nx[l][dir]][!dir];
}

void f (int l, int r, int dir) {
	for (int k = nx[l][dir]; k != r; k = nx[k][dir]) {
		path[l][r][dir] = max (dp[l][r][dir], path[l][k][dir] + path[k][r][dir]);
		dp[l][r][dir] = max (dp[l][r][dir], path[l][k][dir] + dp[k][r][dir]);
	}

	dp_max[l][r][dir] = max (dp[l][r][dir], dp_max[l][nx[r][!dir]][dir]);
}

int main () {
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int x;
		while (cin >> x && x) {
			g[i][x-1] = 1;
		}

		nx[i][0] = (i + 1) % n;
		nx[i][1] = i ? i - 1 : n - 1;
	}

	for (int k = 1; k < n; k++)
		for (int i = 0; i < n; i++) {
			int l = i, r = (i + k) % n;
			if (g[l][r]) f_edge (l, r, 0);
			if (g[r][l]) f_edge (r, l, 1);
			f (l, r, 0);
			f (r, l, 1);
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int dir = 0; dir < 2; dir++)
				ans[i] = max (ans[i], dp[i][j][dir]);

	if (!k) {
		int ind = max_element(ans, ans + n) - ans;
		cout << ans[ind] << ' ' << ind + 1 << endl;
		return 0;
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int dir = 0; dir < 2; dir++) {
				int k = nx[j][dir];

				while (k != i && !g[k][i]) k = nx[k][dir];

				if (k == i) continue;

				for (int l = nx[k][dir]; l != i; l = nx[l][dir]) {
					int ans_l = max(dp_max[l][nx[k][dir]][!dir], dp_max[l][nx[i][!dir]][dir]);
					if (g[j][l]) ans[k] = max (ans[k], 2 + path[i][j][dir] + ans_l);
					//cout << k << ' ' << i << ' ' << j << ' ' << l << ' ' << 2 + path[i][j][dir] + ans_l << endl;
				}

			}

	int ind = max_element(ans, ans + n) - ans;
	cout << ans[ind] << ' ' << ind + 1 << endl;
}

Subtask #1
5.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Incorrect 1 ms 620 KB Output isn't correct
3 Incorrect 1 ms 748 KB Output isn't correct
4 Incorrect 2 ms 876 KB Output isn't correct
5 Incorrect 2 ms 1004 KB Output isn't correct
6 Incorrect 4 ms 1132 KB Output isn't correct
7 Incorrect 3 ms 1260 KB Output isn't correct
8 Incorrect 6 ms 1388 KB Output isn't correct
9 Incorrect 5 ms 1516 KB Output isn't correct
10 Correct 7 ms 1900 KB Output is correct
11 Incorrect 6 ms 1772 KB Output isn't correct
12 Incorrect 77 ms 3052 KB Output isn't correct
13 Incorrect 227 ms 4460 KB Output isn't correct
14 Incorrect 274 ms 5996 KB Output isn't correct
15 Incorrect 1190 ms 7404 KB Output isn't correct
16 Incorrect 1259 ms 7368 KB Output isn't correct
17 Incorrect 1214 ms 7404 KB Output isn't correct
18 Incorrect 606 ms 7268 KB Output isn't correct
19 Incorrect 1352 ms 7396 KB Output isn't correct
20 Incorrect 1364 ms 7404 KB Output isn't correct