Submission #319327

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
319327	2020-11-04T20:08:56 Z	luciocf	Sailing Race (CEOI12_race)	C++14	40 / 100	281 ms	5220 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4460 KB	Output is correct
2	Incorrect	2 ms	4460 KB	Output isn't correct
3	Incorrect	3 ms	4480 KB	Output isn't correct
4	Incorrect	3 ms	4460 KB	Output isn't correct
5	Correct	3 ms	4460 KB	Output is correct
6	Incorrect	3 ms	4460 KB	Output isn't correct
7	Correct	5 ms	4460 KB	Output is correct
8	Incorrect	4 ms	4480 KB	Output isn't correct
9	Correct	6 ms	4460 KB	Output is correct
10	Correct	13 ms	4588 KB	Output is correct
11	Correct	8 ms	4460 KB	Output is correct
12	Incorrect	18 ms	4588 KB	Output isn't correct
13	Incorrect	33 ms	4588 KB	Output isn't correct
14	Correct	53 ms	4716 KB	Output is correct
15	Incorrect	189 ms	4964 KB	Output isn't correct
16	Incorrect	241 ms	5092 KB	Output isn't correct
17	Incorrect	206 ms	4964 KB	Output isn't correct
18	Correct	71 ms	4836 KB	Output is correct
19	Incorrect	281 ms	5220 KB	Output isn't correct
20	Incorrect	277 ms	5100 KB	Output isn't correct