답안 #284731

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
284731 2020-08-27T23:42:27 Z Lawliet Sailing Race (CEOI12_race) C++17
90 / 100
2109 ms 2680 KB
#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] = 0;

		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

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);
      |    ~~~~~^~~~~~~~~~~
# 결과 실행 시간 메모리 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 3 ms 2432 KB Output is correct
5 Correct 3 ms 2432 KB Output is correct
6 Correct 8 ms 2432 KB Output is correct
7 Correct 6 ms 2432 KB Output is correct
8 Correct 9 ms 2432 KB Output is correct
9 Correct 8 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 Correct 119 ms 2432 KB Output is correct
13 Correct 290 ms 2560 KB Output is correct
14 Correct 171 ms 2560 KB Output is correct
15 Correct 1575 ms 2648 KB Output is correct
16 Correct 1831 ms 2656 KB Output is correct
17 Incorrect 1580 ms 2652 KB Output isn't correct
18 Correct 247 ms 2648 KB Output is correct
19 Correct 2106 ms 2652 KB Output is correct
20 Incorrect 2109 ms 2680 KB Output isn't correct