Submission #284729

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
284729	2020-08-27T23:27:41 Z	Lawliet	Sailing Race (CEOI12_race)	C++17	75 / 100	3000 ms	2600 KB

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

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.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	4 ms	2432 KB	Output is correct
5	Correct	3 ms	2432 KB	Output is correct
6	Correct	11 ms	2432 KB	Output is correct
7	Correct	6 ms	2432 KB	Output is correct
8	Correct	16 ms	2432 KB	Output is correct
9	Correct	8 ms	2432 KB	Output is correct
10	Correct	20 ms	2456 KB	Output is correct
11	Correct	12 ms	2432 KB	Output is correct
12	Correct	516 ms	2496 KB	Output is correct
13	Correct	1022 ms	2548 KB	Output is correct
14	Correct	180 ms	2600 KB	Output is correct
15	Execution timed out	3083 ms	2560 KB	Time limit exceeded
16	Execution timed out	3085 ms	2560 KB	Time limit exceeded
17	Execution timed out	3094 ms	2560 KB	Time limit exceeded
18	Correct	246 ms	2560 KB	Output is correct
19	Execution timed out	3097 ms	2560 KB	Time limit exceeded
20	Execution timed out	3043 ms	2576 KB	Time limit exceeded