Submission #94459

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
94459	2019-01-18T17:45:23 Z	nikolapesic2802	Sailing Race (CEOI12_race)	C++14	100 / 100	1156 ms	6748 KB

race

/*
	- dp1[l][r][a] = path with maximum length for range [l, r], going in direction a, ends at r
	- dp2[l][r][a] = same as dp1 except it doesn't end at r
	- dp3[l][r][a] = max of dp1[l][l..r][a]
	- We can find the answer with these DP's
	- Precompute (i+1)%n and (i-1)%n to not get TLE
*/
#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()

using namespace std;


#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({{dp3[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	504 KB	Output is correct
2	Correct	2 ms	632 KB	Output is correct
3	Correct	2 ms	712 KB	Output is correct
4	Correct	2 ms	888 KB	Output is correct
5	Correct	3 ms	1016 KB	Output is correct
6	Correct	5 ms	1144 KB	Output is correct
7	Correct	4 ms	1276 KB	Output is correct
8	Correct	23 ms	1400 KB	Output is correct
9	Correct	6 ms	1400 KB	Output is correct
10	Correct	7 ms	1656 KB	Output is correct
11	Correct	7 ms	1656 KB	Output is correct
12	Correct	67 ms	2808 KB	Output is correct
13	Correct	197 ms	4216 KB	Output is correct
14	Correct	289 ms	5340 KB	Output is correct
15	Correct	1025 ms	6648 KB	Output is correct
16	Correct	1085 ms	6520 KB	Output is correct
17	Correct	987 ms	6748 KB	Output is correct
18	Correct	545 ms	6520 KB	Output is correct
19	Correct	1156 ms	6648 KB	Output is correct
20	Correct	1090 ms	6668 KB	Output is correct