Submission #680470

#	Time	Username	Problem	Language	Result	Execution time	Memory
680470		kingfran1907	Sailing Race (CEOI12_race)	C++14	100 / 100	2264 ms	6964 KiB

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) {
	if (l == x) return 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) || tren == i) 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) || tren == i) 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 (stderr)

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

• Subtask 1: 100 / 100