Submission #284722

#	Time	Username	Problem	Language	Result	Execution time	Memory
284722		Lawliet	Sailing Race (CEOI12_race)	C++17	40 / 100	709 ms	2936 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;
}

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;
			}
		}
	}
	
	printf("%d\n",ans);
	printf("%d\n",optS);
}

Compilation message (stderr)

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

• Subtask 1: 40 / 100