Submission #79463

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
79463	2018-10-14T05:28:14 Z	tmwilliamlin168	Sailing Race (CEOI12_race)	C++14	75 / 100	3000 ms	7564 KB

race

#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

#	Verdict	Execution time	Memory	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