답안 #680468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680468	2023-01-10T23:53:34 Z	kingfran1907	Sailing Race (CEOI12_race)	C++17	40 / 100	539 ms	2932 KB

race

#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

40.0 / 100.0

#	결과	실행 시간	메모리	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