Submission #284729

#	Time	Username	Problem	Language	Result	Execution time	Memory
284729		Lawliet	Sailing Race (CEOI12_race)	C++17	75 / 100	3097 ms	2600 KiB

race

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 510;

int n, k;

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);
}

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;

		for(int i = mod(T - 1); i != T ; i = mod(i - 1))
		{
			maxPath[i] = 0;

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

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

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

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

				curAns++;

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

		for(int i = mod(T + 1) ; i != T ; i = mod(i + 1))
		{
			maxPath[i] = 0;

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

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

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

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

				curAns++;

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

	answer( ans , optS );
}

Compilation message (stderr)

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

• Subtask 1: 75 / 100