Submission #680468

# Submission time Handle Problem Language Result Execution time Memory
680468 2023-01-10T23:53:34 Z kingfran1907 Sailing Race (CEOI12_race) C++17
40 / 100
539 ms 2932 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);
      |    ~~~~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Incorrect 1 ms 2260 KB Output isn't correct
3 Incorrect 1 ms 2260 KB Output isn't correct
4 Incorrect 2 ms 2260 KB Output isn't correct
5 Correct 2 ms 2260 KB Output is correct
6 Incorrect 2 ms 2260 KB Output isn't correct
7 Correct 6 ms 2388 KB Output is correct
8 Incorrect 3 ms 2260 KB Output isn't correct
9 Correct 9 ms 2388 KB Output is correct
10 Correct 23 ms 2388 KB Output is correct
11 Correct 11 ms 2424 KB Output is correct
12 Incorrect 31 ms 2500 KB Output isn't correct
13 Incorrect 49 ms 2388 KB Output isn't correct
14 Correct 107 ms 2492 KB Output is correct
15 Incorrect 309 ms 2680 KB Output isn't correct
16 Incorrect 411 ms 2916 KB Output isn't correct
17 Incorrect 346 ms 2764 KB Output isn't correct
18 Correct 106 ms 2516 KB Output is correct
19 Incorrect 493 ms 2928 KB Output isn't correct
20 Incorrect 539 ms 2932 KB Output isn't correct