Submission #113362

#	Time	Username	Problem	Language	Result	Execution time	Memory
113362		ckodser	Sailing Race (CEOI12_race)	C++14	30 / 100	1490 ms	4856 KiB

race

#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int n, tp, Next[N], Prev[N], dp[N][N][2], dp2[N][N][2];
bool M[N][N];
inline void smax(int &a, int b){a = max(a, b);}
int main()
{
	scanf("%d%d", &n, &tp);
	for (int i = 0; i < n; i++)
	{
		int a;
		scanf("%d", &a);
		while (a)
			M[i][a - 1] = 1, scanf("%d", &a);
	}
	for (int i = 0; i < n - 1; i++)
		Next[i] = i + 1;
	Next[n - 1] = 0;
	for (int i = 1; i < n; i++)
		Prev[i] = i - 1;
	Prev[0] = n - 1;
	memset(dp, -63, sizeof(dp));
	memset(dp2, -63, sizeof(dp2));
	for (int i = 0; i < n; i++)
		dp[i][i][0] = dp[i][i][1] = 0;
	for (int len = 2; len <= n; len ++)
		for (int l = 0; l < n; l ++)
		{
			int r = (l + len - 1) % n;
			// 0
			for (int j = Next[l]; j != Next[r]; j = Next[j])
				if (M[l][j])
					smax(dp[l][r][0], dp[j][r][0] + 1);
			// 1
			for (int j = l; j != r; j = Next[j])
				if (M[r][j])
					smax(dp[l][r][1], dp[l][j][1] + 1);
		}
	for (int i = 0; i < n; i++)
		dp2[i][i][0] = dp2[i][i][1] = 0;
	for (int len = 2; len <= n; len ++)
		for (int l = 0; l < n; l ++)
		{
			int r = (l + len - 1) % n;
			// 0
			for (int j = Next[l]; j != Next[r]; j = Next[j])
				if (M[l][j])
					smax(dp2[l][r][0], max(dp2[j][r][0] + 1, dp2[Next[l]][j][1] + 1));
			// 1
			for (int j = l; j != r; j = Next[j])
				if (M[r][j])
					smax(dp2[l][r][1], max(dp2[l][j][1] + 1, dp2[j][Prev[r]][0] + 1));
		}

	/*while (1)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		a --; b --;
		printf("%d ::\n", dp2[a][b][c]);
	}*/

	int Mx = -1, st = -1;
	for (int l = 0; l < n; l ++)
		for (int r = 0; r < n; r ++)
			if (M[l][r])
			{
				bool w = (l < r);
				if (Mx < max(dp2[Next[l]][r][w], dp2[r][Prev[l]][!w]))
					Mx = max(dp2[Next[l]][r][w], dp2[r][Prev[l]][!w]), st = l;
			}

	if (!tp)
		return !printf("%d\n%d\n", Mx, st + 1);

	for (int b = 0; b < n; b ++)
		for (int c = 0; c < n; c ++)
			if (b != c)
			{
				int a = -1;
				for (int i = Next[c]; i != b; i = Next[i])
					if (M[i][b])
					{
						a = i;
						break;
					}
				if (a == -1)
					continue;
				for (int d = Next[a]; d != b; d = Next[d])
				{
					if (!M[c][d])
						continue;
					int res = 2 + dp[b][c][0] + max(dp2[d][Prev[b]][0], dp2[Next[a]][d][1]);
					if (Mx < res)
						Mx = res, st = a;
				}
			}
	for (int b = 0; b < n; b ++)
		for (int c = 0; c < n; c ++)
			if (b != c)
			{
				int a = -1;
				for (int i = Prev[c]; i != b; i = Prev[i])
					if (M[i][b])
					{
						a = i;
						break;
					}
				if (a == -1)
					continue;
				for (int d = Prev[a]; d != b; d = Prev[d])
				{
					if (!M[c][d])
						continue;
					int res = 2 + dp[c][b][1] + max(dp2[Prev[b]][d][1], dp2[d][Next[a]][0]);
					if (Mx < res)
						Mx = res, st = a;
				}
			}
	return !printf("%d\n%d\n", Mx, st + 1);
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &tp);
  ~~~~~^~~~~~~~~~~~~~~~~
race.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~
race.cpp:15:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    M[i][a - 1] = 1, scanf("%d", &a);
    ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 100