oj.uz

Submission #79465

# Submission time Handle Problem Language Result Execution time Memory
79465 2018-10-14T05:31:08 Z tmwilliamlin168 Sailing Race (CEOI12_race) C++14
75 / 100
 3000 ms 6776 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]<=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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 628 KB Output is correct
3 Correct 2 ms 816 KB Output is correct
4 Correct 4 ms 944 KB Output is correct
5 Correct 4 ms 944 KB Output is correct
6 Correct 8 ms 1028 KB Output is correct
7 Correct 8 ms 1284 KB Output is correct
8 Correct 16 ms 1348 KB Output is correct
9 Correct 13 ms 1476 KB Output is correct
10 Correct 18 ms 1732 KB Output is correct
11 Correct 19 ms 1732 KB Output is correct
12 Correct 227 ms 2940 KB Output is correct
13 Correct 686 ms 4328 KB Output is correct
14 Correct 925 ms 5608 KB Output is correct
15 Execution timed out 3035 ms 6648 KB Time limit exceeded
16 Execution timed out 3059 ms 6648 KB Time limit exceeded
17 Execution timed out 3061 ms 6648 KB Time limit exceeded
18 Correct 1808 ms 6648 KB Output is correct
19 Execution timed out 3054 ms 6648 KB Time limit exceeded
20 Execution timed out 3049 ms 6776 KB Time limit exceeded