oj.uz

답안 #79463

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
79463 2018-10-14T05:28:14 Z tmwilliamlin168 Sailing Race (CEOI12_race) C++14
75 / 100
 3000 ms 7564 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=500;
int n, ai, dp[mxN][mxN][2][2], dp2[mxN][mxN][2];
bool k, adj[mxN][mxN];
array<int, 2> ans;

void c(int l, int r, int a) {
	int d=a?1:-1;
	if(adj[l][r]) {
		dp[l][r][a][0]=1;
		dp[l][r][a][1]=1+dp2[r][(l+d+n)%n][a^1];
	} else
		dp[l][r][a][0]=dp[l][r][a][1]=-n;
	for(int k=(l+d+n)%n; k!=r; k=(k+d+n)%n)
		for(int i=0; i<2; ++i)
			dp[l][r][a][i]=max(dp[l][k][a][0]+dp[k][r][a][i], dp[l][r][a][i]);
//	cout << l << " " << r << " " << a << " " << dp[l][r][a][0] << " " << dp[l][r][a][1] << endl;
	dp2[l][r][a]=max(dp[l][r][a][1], dp2[l][(r-d+n)%n][a]);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	for(int i=0; i<n; ++i) {
		cin >> ai;
		while(ai) {
			adj[i][ai-1]=1;
			cin >> ai;
		}
	}
	for(int l=1; l<n; ++l) {
		for(int i=0; i<n; ++i) {
			c(i, (i+l)%n, 1);
			c((i+l)%n, i, 0);
		}
	}
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j)
			for(int k=0; k<2; ++k)
				ans=max({{dp[i][j][k][1], i}, ans});
	if(k) {
		for(int i=0; i<n; ++i) {
			for(int j=0; j<n; ++j) {
				for(int a=0, d=-1; a<2; ++a, d=-d) {
					if(!dp[i][j][a][0])
						continue;
					int k=(j+d+n)%n;
					for(; k!=i&&!adj[k][i]; k=(k+d+n)%n);
					if(k!=i)
						for(int l=(k+d+n)%n; l!=i; l=(l+d+n)%n)
							if(adj[j][l])
								ans=max({{2+dp[i][j][a][0]+max(dp2[l][(k+d+n)%n][a^1], dp2[l][(i-d+n)%n][a]), k}, ans});
				}
			}
		}
	}
	cout << ans[0] << "\n" << ans[1]+1;
}

Subtask #1
75.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 624 KB Output is correct
3 Correct 3 ms 700 KB Output is correct
4 Correct 4 ms 976 KB Output is correct
5 Correct 4 ms 976 KB Output is correct
6 Correct 9 ms 1164 KB Output is correct
7 Correct 8 ms 1340 KB Output is correct
8 Correct 18 ms 1356 KB Output is correct
9 Correct 13 ms 1500 KB Output is correct
10 Correct 18 ms 1768 KB Output is correct
11 Correct 17 ms 1768 KB Output is correct
12 Correct 238 ms 3088 KB Output is correct
13 Correct 761 ms 4540 KB Output is correct
14 Correct 917 ms 5724 KB Output is correct
15 Execution timed out 3049 ms 6956 KB Time limit exceeded
16 Execution timed out 3040 ms 7028 KB Time limit exceeded
17 Execution timed out 3052 ms 7164 KB Time limit exceeded
18 Correct 1840 ms 7400 KB Output is correct
19 Execution timed out 3070 ms 7564 KB Time limit exceeded
20 Execution timed out 3050 ms 7564 KB Time limit exceeded