oj.uz

답안 #319327

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319327 2020-11-04T20:08:56 Z luciocf Sailing Race (CEOI12_race) C++14
40 / 100
 281 ms 5220 KB 
#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

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