Submission #79463

#	Time	Username	Problem	Language	Result	Execution time	Memory
79463		tmwilliamlin168	Sailing Race (CEOI12_race)	C++14	75 / 100	3070 ms	7564 KiB

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 / 100