답안 #284722

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
284722 2020-08-27T23:02:08 Z Lawliet Sailing Race (CEOI12_race) C++17
40 / 100
709 ms 2936 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;
}

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);
      |    ~~~~~^~~~~~~~~~~
# 결과 실행 시간 메모리 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