oj.uz

답안 #680467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680467 2023-01-10T23:47:52 Z vjudge1 Sailing Race (CEOI12_race) C++17
70 / 100
 2059 ms 7140 KB 
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 510;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, k;
vector< int > graph[maxn], graph2[maxn];
int dp[maxn][maxn][2];
int dist[2][maxn][maxn];
int bes[maxn][maxn][2];

int dis(int x, int y, bool flag = false) {
	if (flag) swap(x, y);
	return (y - x + n) % n;
}

bool check(int l, int r, int x, bool flag = false) {
	return dis(l, x, flag) < dis(l, r, flag);
}

int f(int l, int r, bool flag) {
	int &ret = dp[l][r][flag];
	if (ret != -1) return ret;

	ret = 0;
	for (int tren : graph[l]) {
		if (check(l, r, tren, flag)) 
			ret = max(ret, 1 + max(f(tren, l, !flag), f(tren, r, flag)));
	}
	return ret;
}

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		while (true) {
			int x;
			scanf("%d", &x);
			if (x == 0) break;
			graph[i].push_back(x - 1);
			graph2[x - 1].push_back(i);
		}
	}

	pair<int, int> sol = {-1, -1};
	memset(dp, -1, sizeof dp);
	for (int i = 0; i < n; i++) {
		for (int tren : graph[i]) {
			for (int k = 0; k < 2; k++) {
				sol = max(sol, {1 + f(tren, i, k), i});
			}
		}
	}
	if (k == 0) {
		printf("%d\n%d\n", sol.X, sol.Y + 1);
		return 0;
	}

	for (int i = 0; i < n; i++) {
		for (int j = (i + 1) % n; j != i; j++, j %= n) {
			dist[0][i][j] = -inf;
			for (int tren : graph2[j]) {
				if (check(i, j, tren)) dist[0][i][j] = max(dist[0][i][j], 1 + dist[0][i][tren]);
			}
		}
		for (int j = (i + n - 1) % n; j != i; j += n - 1, j %= n) {
			dist[1][i][j] = -inf;
			for (int tren : graph2[j]) {
				if (check(i, j, tren, 1)) dist[1][i][j] = max(dist[1][i][j], 1 + dist[1][i][tren]);
			}
		}
	}

	memset(bes, -1, sizeof bes);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int tren : graph2[i]) {
				for (int k = 0; k < 2; k++) {
					if (check(i, j, tren, k)) continue;
					if (bes[i][j][k] == -1) bes[i][j][k] = tren;
					else if (dis(i, tren, k) < dis(i, bes[i][j][k], k)) bes[i][j][k] = tren;
				}
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < 2; k++) {
				if (i == j) continue;
				for (int tren : graph[j]) {
					int tr = bes[i][j][k];
					if (tr == -1) continue;
					if (!check(j, tren, tr, k) || !check(i, j, tren, 1 - k)) continue;

					int ac = dist[k][i][j] + 2 + max(f(tren, tr, 1 - k), f(tren, i, k));
					//printf("%d -> %d -> %d -> %d --- %d (%d)\n", tr, i, j, tren, ac, k);
					//printf("%d + (%d %d)\n", dist[k][i][j], f(tren, tr, 1 - k), f(tren, i, k));
					sol = max(sol, {ac, tr});
				}
			}
		}
	}

	printf("%d\n%d\n", sol.X, sol.Y + 1);
	return 0;
}

Compilation message

race.cpp: In function 'int main()':
race.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
race.cpp:48:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~

Subtask #1
70.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2256 KB Output is correct
2 Incorrect 3 ms 4436 KB Output isn't correct
3 Correct 3 ms 4436 KB Output is correct
4 Incorrect 4 ms 4564 KB Output isn't correct
5 Correct 3 ms 2388 KB Output is correct
6 Correct 7 ms 4564 KB Output is correct
7 Correct 6 ms 2388 KB Output is correct
8 Correct 10 ms 4632 KB Output is correct
9 Correct 7 ms 2388 KB Output is correct
10 Correct 27 ms 2496 KB Output is correct
11 Correct 14 ms 2396 KB Output is correct
12 Incorrect 118 ms 5288 KB Output isn't correct
13 Correct 202 ms 5684 KB Output is correct
14 Correct 91 ms 2516 KB Output is correct
15 Correct 1230 ms 6832 KB Output is correct
16 Incorrect 1738 ms 6972 KB Output isn't correct
17 Incorrect 1332 ms 6816 KB Output isn't correct
18 Correct 113 ms 2544 KB Output is correct
19 Correct 1963 ms 7140 KB Output is correct
20 Incorrect 2059 ms 7072 KB Output isn't correct