Submission #90461

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90461	2018-12-21T17:17:55 Z	nikolapesic2802	Sailing Race (CEOI12_race)	C++14	100 / 100	1133 ms	8060 KB

race

#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], b[mxN][2];
bool k, adj[mxN][mxN];
array<int, 2> ans;

void c(int l, int r, int a) {
	if(adj[l][r]) {
		dp1[l][r][a]=1;
		dp2[l][r][a]=1+dp3[r][b[l][a]][a^1];
	} else
		dp1[l][r][a]=dp2[l][r][a]=-n;
	for(int k=b[l][a]; k!=r; k=b[k][a]) {
		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], dp2[l][r][a]);
	}
	dp3[l][r][a]=max(dp2[l][r][a], dp3[l][b[r][a^1]][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;
		}
		b[i][0]=(i+n-1)%n;
		b[i][1]=(i+1)%n;
	}
	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; a<2; ++a) {
					if(dp1[i][j][a]<=0)
						continue;
					int k=b[j][a];
					for(; k!=i&&!adj[k][i]; k=b[k][a]);
					if(k!=i)
						for(int l=b[k][a]; l!=i; l=b[l][a])
							if(adj[j][l])
								ans=max({{2+dp1[i][j][a]+max(dp3[l][b[k][a]][a^1], dp3[l][b[i][a^1]][a]), k}, ans});
				}
			}
		}
	}
	cout << ans[0] << "\n" << ans[1]+1;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	632 KB	Output is correct
2	Correct	2 ms	824 KB	Output is correct
3	Correct	2 ms	1112 KB	Output is correct
4	Correct	2 ms	1328 KB	Output is correct
5	Correct	3 ms	1376 KB	Output is correct
6	Correct	4 ms	1524 KB	Output is correct
7	Correct	4 ms	1704 KB	Output is correct
8	Correct	6 ms	1752 KB	Output is correct
9	Correct	5 ms	2028 KB	Output is correct
10	Correct	7 ms	2060 KB	Output is correct
11	Correct	7 ms	2092 KB	Output is correct
12	Correct	67 ms	3488 KB	Output is correct
13	Correct	193 ms	4732 KB	Output is correct
14	Correct	275 ms	6008 KB	Output is correct
15	Correct	1022 ms	7368 KB	Output is correct
16	Correct	1053 ms	7472 KB	Output is correct
17	Correct	977 ms	7740 KB	Output is correct
18	Correct	576 ms	7740 KB	Output is correct
19	Correct	1133 ms	7892 KB	Output is correct
20	Correct	1132 ms	8060 KB	Output is correct