Submission #284731

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
284731	2020-08-27T23:42:27 Z	Lawliet	Sailing Race (CEOI12_race)	C++17	90 / 100	2109 ms	2680 KB

race

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 510;

int n, k;

int maxVal[MAXN];
int maxPath[MAXN];
int dp[MAXN][MAXN][2];

bool adj[MAXN][MAXN];

int mod(int k)
{
	if( k > n ) return k - n;
	if( k <= 0 ) return k + n; 
 	return k;
}

int solve(int L, int R, int t)
{
	int& ans = dp[L][R][t];

	if( ans != -1 ) return ans;
	if( L == R ) return 0;

	ans = 0;

	if( t == 0 )
	{
		for(int newR = mod(R - 1) ; newR != L ; newR = mod(newR - 1) )
		{
			if( !adj[L][newR] ) continue;

			ans = max( ans , solve( L , newR , 1 ) + 1 );
			ans = max( ans , solve( newR , R , 0 ) + 1 );
		}
	}

	if( t == 1 )
	{
		for(int newL = mod(L + 1) ; newL != R ; newL = mod(newL + 1) )
		{
			if( !adj[R][newL] ) continue;

			ans = max( ans , solve( L , newL , 1 ) + 1 );
			ans = max( ans , solve( newL , R , 0 ) + 1 );
		}
	}

	return ans;
}

void answer(int maxLength, int start)
{
	printf("%d\n",maxLength);
	printf("%d\n",start);

	exit(0);
}

void calculateBestPath(int T, int c)
{
	for(int i = mod(T + c); i != T ; i = mod(i + c))
	{
		maxPath[i] = 0;

		for(int j = T ; j != i ; j = mod(j + c) )
			if( adj[j][i] ) maxPath[i] = max( maxPath[i] , maxPath[j] + 1 );
	}
}

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

	for(int i = 1 ; i <= n ; i++)
	{
		int viz;
		scanf("%d",&viz);

		while( viz != 0 )
		{
			adj[i][viz] = true;
			scanf("%d",&viz);
		}
	}

	memset( dp , -1 , sizeof(dp) );

	int ans = 0;
	int optS = 1;

	for(int S = 1 ; S <= n ; S++)
	{
		for(int T = 1 ; T <= n ; T++)
		{
			if( !adj[S][T] ) continue;

			int curAns = solve( S , T , 1 ) + 1;
			curAns = max( curAns , solve( T , S , 0 ) + 1 );

			if( ans < curAns )
			{
				optS = S;
				ans = curAns;
			}
		}
	}

	if( k == 0 ) answer( ans , optS );

	for(int T = 1 ; T <= n ; T++)
	{
		maxPath[T] = 0;
		calculateBestPath( T , -1 );

		for(int i = 1 ; i <= n ; i++)
			maxVal[i] = -1;

		for(int S = mod(T - 1) ; S != T ; S = mod(S - 1))
		{
			if( adj[S][T] )
			{
				int curAns = 0;

				for(int B = mod(S - 1) ; B != T ; B = mod(B - 1))
				{
					if( maxVal[B] == -1 ) continue;
					
					int val = max( solve( B , S , 0 ) , solve( T , B , 1 ) );
					val += maxVal[B];

					curAns = max( curAns , val + 1 );
				}

				curAns++;

				if( ans < curAns )
				{
					optS = S;
					ans = curAns;
				}
			}

			for(int B = mod(S - 1) ; B != T ; B = mod(B - 1))
				if( adj[S][B] ) maxVal[B] = max( maxVal[B] , maxPath[S] );
		}	

		calculateBestPath( T , 1 );

		for(int i = 1 ; i <= n ; i++)
			maxVal[i] = -1;

		for(int S = mod(T + 1) ; S != T ; S = mod(S + 1))
		{
			if( adj[S][T] )
			{
				int curAns = 0;

				for(int B = mod(T - 1) ; B != S ; B = mod(B - 1))
				{
					if( maxVal[B] == -1 ) continue;
					
					int val = max( solve( S , B , 1 ) , solve( B , T , 0 ) );
					val += maxVal[B];

					curAns = max( curAns , val + 1 );
				}

				curAns++;

				if( ans < curAns )
				{
					optS = S;
					ans = curAns;
				}
			}

			for(int B = mod(T - 1) ; B != S ; B = mod(B - 1))
				if( adj[S][B] ) maxVal[B] = max( maxVal[B] , maxPath[S] );
		}	
	}

	answer( ans , optS );
}

Compilation message

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

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2304 KB	Output is correct
2	Correct	2 ms	2304 KB	Output is correct
3	Correct	2 ms	2304 KB	Output is correct
4	Correct	3 ms	2432 KB	Output is correct
5	Correct	3 ms	2432 KB	Output is correct
6	Correct	8 ms	2432 KB	Output is correct
7	Correct	6 ms	2432 KB	Output is correct
8	Correct	9 ms	2432 KB	Output is correct
9	Correct	8 ms	2432 KB	Output is correct
10	Correct	15 ms	2432 KB	Output is correct
11	Correct	12 ms	2432 KB	Output is correct
12	Correct	119 ms	2432 KB	Output is correct
13	Correct	290 ms	2560 KB	Output is correct
14	Correct	171 ms	2560 KB	Output is correct
15	Correct	1575 ms	2648 KB	Output is correct
16	Correct	1831 ms	2656 KB	Output is correct
17	Incorrect	1580 ms	2652 KB	Output isn't correct
18	Correct	247 ms	2648 KB	Output is correct
19	Correct	2106 ms	2652 KB	Output is correct
20	Incorrect	2109 ms	2680 KB	Output isn't correct