Submission #284734

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
284734	2020-08-27T23:55:28 Z	Lawliet	Sailing Race (CEOI12_race)	C++17	100 / 100	2217 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] = -1;
 
		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

100.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	6 ms	2432 KB	Output is correct
7	Correct	6 ms	2432 KB	Output is correct
8	Correct	8 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	2556 KB	Output is correct
13	Correct	294 ms	2552 KB	Output is correct
14	Correct	166 ms	2680 KB	Output is correct
15	Correct	1611 ms	2652 KB	Output is correct
16	Correct	1863 ms	2680 KB	Output is correct
17	Correct	1659 ms	2680 KB	Output is correct
18	Correct	253 ms	2560 KB	Output is correct
19	Correct	2103 ms	2680 KB	Output is correct
20	Correct	2217 ms	2656 KB	Output is correct