Submission #319327

#	Time	Username	Problem	Language	Result	Execution time	Memory
319327		luciocf	Sailing Race (CEOI12_race)	C++14	40 / 100	281 ms	5220 KiB

race

#include <bits/stdc++.h>

using namespace std;

const int maxn = 510;

int n, k;

vector<int> grafo[maxn];

int dp[maxn][maxn][2][2];

bool liga[maxn][maxn];

int solve(int l, int r, int dir, int q)
{
	if (l == r) return 0;
	if (dp[l][r][dir][q] != -1) return dp[l][r][dir][q];

	int ans = 0;
	int u = (!q ? l : r);

	if (dir == 0)
	{
		for (auto v: grafo[u])
		{
			if (v > l && v < r)
			{
				ans = max(ans, 1 + solve(l, v, 0, 1));
				ans = max(ans, 1 + solve(v, r, 0, 0));
			}
		}
	}
	else
	{
		for (auto v: grafo[u])
		{
			if (v < l)
			{
				ans = max(ans, 1 + solve(v, l, 0, 0));
				ans = max(ans, 1 + solve(v, r, 1, 0));
			}
			else if (v > r)
			{
				ans = max(ans, 1 + solve(l, v, 1, 1));
				ans = max(ans, 1 + solve(r, v, 0, 1));
			}
		}
	}

	return dp[l][r][dir][q] = ans;
}

int main(void)
{
	scanf("%d %d", &n, &k);

	for (int i = 0; i < n; i++)
	{
		int x;
		while (scanf("%d", &x))
		{
			if (!x) break;

			grafo[i].push_back(x-1);
			liga[i][x-1] = 1;
		}
	}

	memset(dp, -1, sizeof dp);

	int ans = 0, best = 0;

	for (int l = 0; l < n; l++)
	{
		for (int r = l+1; r < n; r++)
		{
			if (liga[r][l] && 1 + solve(l, r, 0, 0) > ans)
				ans = 1 + solve(l, r, 0, 0), best = r;

			if (liga[l][r] && 1 + solve(l, r, 0, 1) > ans)
				ans = 1 + solve(l, r, 0, 1), best = l;

			if (liga[r][l] && 1 + solve(l, r, 1, 0) > ans)
				ans = 1 + solve(l, r, 1, 0), best = r;

			if (liga[l][r] && 1 + solve(l, r, 1, 1) > ans)
				ans = 1 + solve(l, r, 1, 1), best = l;
		}
	}

	printf("%d\n%d\n", ans, best+1);
}

Compilation message (stderr)

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

• Subtask 1: 40 / 100