oj.uz

Submission #79467

# Submission time Handle Problem Language Result Execution time Memory
79467 2018-10-14T05:35:16 Z tmwilliamlin168 Sailing Race (CEOI12_race) C++14
10 / 100
 3000 ms 6756 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=500;
int n, ai, dp1[mxN][mxN][2], dp2[mxN][mxN][2], dp3[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]) {
		dp1[l][r][a]=1;
		dp2[l][r][a]=1+dp3[r][(l+d+n)%n][a^1];
	} else
		dp1[l][r][a]=dp2[l][r][a]=-n;
	for(int k=(l+d+n)%n; k!=r; k=(k+d+n)%n) {
		dp1[l][r][a]=max(dp1[l][k][a]+dp1[k][r][a], dp1[l][r][a]);
		dp2[l][r][a]=max(dp1[l][k][a]+dp2[k][r][a], dp1[l][r][a]);
	}
	dp3[l][r][a]=max(dp2[l][r][a], dp3[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({{dp2[i][j][k], 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(dp1[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+dp1[i][j][a]+max(dp3[l][(k+d+n)%n][a^1], dp3[l][(i-d+n)%n][a]), k}, ans});
				}
			}
		}
	}
	cout << ans[0] << "\n" << ans[1]+1;
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 760 KB Output isn't correct
3 Incorrect 3 ms 824 KB Output isn't correct
4 Incorrect 4 ms 952 KB Output isn't correct
5 Incorrect 4 ms 1124 KB Output isn't correct
6 Incorrect 8 ms 1144 KB Output isn't correct
7 Incorrect 7 ms 1272 KB Output isn't correct
8 Incorrect 15 ms 1400 KB Output isn't correct
9 Incorrect 13 ms 1548 KB Output isn't correct
10 Correct 17 ms 1656 KB Output is correct
11 Incorrect 18 ms 1796 KB Output isn't correct
12 Incorrect 220 ms 2992 KB Output isn't correct
13 Incorrect 674 ms 4304 KB Output isn't correct
14 Incorrect 889 ms 5584 KB Output isn't correct
15 Execution timed out 3023 ms 6608 KB Time limit exceeded
16 Execution timed out 3026 ms 6756 KB Time limit exceeded
17 Execution timed out 3049 ms 6756 KB Time limit exceeded
18 Incorrect 1728 ms 6756 KB Output isn't correct
19 Execution timed out 3041 ms 6756 KB Time limit exceeded
20 Execution timed out 3053 ms 6756 KB Time limit exceeded