Submission #284722

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
284722	2020-08-27T23:02:08 Z	Lawliet	Sailing Race (CEOI12_race)	C++17	40 / 100	709 ms	2936 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;
}

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2304 KB	Output is correct
2	Incorrect	2 ms	2304 KB	Output isn't correct
3	Incorrect	2 ms	2304 KB	Output isn't correct
4	Incorrect	2 ms	2432 KB	Output isn't correct
5	Correct	3 ms	2432 KB	Output is correct
6	Incorrect	3 ms	2432 KB	Output isn't correct
7	Correct	6 ms	2432 KB	Output is correct
8	Incorrect	4 ms	2432 KB	Output isn't correct
9	Correct	9 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	Incorrect	41 ms	2560 KB	Output isn't correct
13	Incorrect	86 ms	2680 KB	Output isn't correct
14	Correct	166 ms	2680 KB	Output is correct
15	Incorrect	507 ms	2760 KB	Output isn't correct
16	Incorrect	608 ms	2688 KB	Output isn't correct
17	Incorrect	513 ms	2808 KB	Output isn't correct
18	Correct	246 ms	2688 KB	Output is correct
19	Incorrect	709 ms	2936 KB	Output isn't correct
20	Incorrect	699 ms	2936 KB	Output isn't correct