oj.uz

답안 #284734

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
284734 2020-08-27T23:55:28 Z Lawliet Sailing Race (CEOI12_race) C++17
100 / 100
 2217 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] = -1;
 
		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);
      |    ~~~~~^~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 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 6 ms 2432 KB Output is correct
7 Correct 6 ms 2432 KB Output is correct
8 Correct 8 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 2556 KB Output is correct
13 Correct 294 ms 2552 KB Output is correct
14 Correct 166 ms 2680 KB Output is correct
15 Correct 1611 ms 2652 KB Output is correct
16 Correct 1863 ms 2680 KB Output is correct
17 Correct 1659 ms 2680 KB Output is correct
18 Correct 253 ms 2560 KB Output is correct
19 Correct 2103 ms 2680 KB Output is correct
20 Correct 2217 ms 2656 KB Output is correct