oj.uz

Submission #79469

# Submission time Handle Problem Language Result Execution time Memory
79469 2018-10-14T05:39:17 Z tmwilliamlin168 Sailing Race (CEOI12_race) C++14
10 / 100
 1340 ms 6784 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], 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], dp1[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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 628 KB Output isn't correct
3 Incorrect 2 ms 792 KB Output isn't correct
4 Incorrect 3 ms 1040 KB Output isn't correct
5 Incorrect 4 ms 1096 KB Output isn't correct
6 Incorrect 5 ms 1284 KB Output isn't correct
7 Incorrect 4 ms 1300 KB Output isn't correct
8 Incorrect 7 ms 1556 KB Output isn't correct
9 Incorrect 7 ms 1616 KB Output isn't correct
10 Correct 9 ms 1760 KB Output is correct
11 Incorrect 8 ms 1772 KB Output isn't correct
12 Incorrect 82 ms 3052 KB Output isn't correct
13 Incorrect 246 ms 4328 KB Output isn't correct
14 Incorrect 319 ms 5500 KB Output isn't correct
15 Incorrect 1204 ms 6784 KB Output isn't correct
16 Incorrect 1227 ms 6784 KB Output isn't correct
17 Incorrect 1153 ms 6784 KB Output isn't correct
18 Incorrect 647 ms 6784 KB Output isn't correct
19 Incorrect 1330 ms 6784 KB Output isn't correct
20 Incorrect 1340 ms 6784 KB Output isn't correct