Submission #284734

#	Time	Username	Problem	Language	Result	Execution time	Memory
284734		Lawliet	Sailing Race (CEOI12_race)	C++17	100 / 100	2217 ms	2680 KiB

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 (stderr)

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 / 100