Submission #132263

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
132263	2019-07-18T15:32:28 Z	amoo_safar	Sailing Race (CEOI12_race)	C++14	100 / 100	2081 ms	2756 KB

race

#include<bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;

const int Maxn = 5e2 + 10;
const int Inf = 10000;
bool G[Maxn][Maxn];

int n, dp[Maxn][Maxn][2], dp2[Maxn], dp3[Maxn];

int nxt(int y){
	return (y == n - 1 ? 0 : y + 1);
}
int prev(int y){
	return (y == 0 ? n - 1 : y- 1);
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int k;
	cin >> n >> k;
	
	int adj;
	for(int i = 0; i < n; i++){
		while(true){
			cin >> adj;
			adj --;
			if(adj == -1) break;
			G[i][adj] = true;
		}
	}
	
	for(int l = 1; l <= n; l++){
		for(int i = 0; i < n; i++){
			int j = (i + l) % n;
			dp[i][j][0] = 0;
			for(int k = nxt(i); k != j; k = nxt(k)){
				if(G[i][k]) dp[i][j][0] = max( dp[i][j][0], max(dp[k][j][0], dp[k][i][1]) + 1);
			}
			j = (i - l + n) % n;
			dp[i][j][1] = 0;
			for(int k = prev(i); k != j; k = prev(k)){
				if(G[i][k]) dp[i][j][1] = max( dp[i][j][1], max(dp[k][j][1], dp[k][i][0]) + 1);
			}
		}
	}
	int ans = 0, st = 0, res;
	for(int i = 0; i < n; i++){
		ans = max(ans, dp[i][i][0]);
		if(ans == dp[i][i][0]) st = i;
	}
	
	if(k == 1){
		for(int sec = 0; sec < n; sec ++){
			fill(dp2, dp2 + Maxn, -Inf);
			dp2[sec] = 0;
			for(int fir = nxt(sec); fir != sec; fir = nxt(fir)){
				for(int bef = sec; bef != fir; bef = nxt(bef)){
					if(G[bef][fir]) dp2[fir] = max(dp2[fir], dp2[bef] + 1);
				}
			}
			fill(dp3, dp3 + Maxn, -Inf);
			for(int fir = nxt(sec); fir != sec; fir = nxt(fir)){
				
				if((fir != nxt(sec)) && (G[fir][sec])){
					res = 0;
					for(int P = nxt(fir); P != sec; P = nxt(P)){
						res = max(res, 1 + dp3[P] + max(dp[P][sec][0], dp[P][fir][1]) );
					}
					if(res > ans){
						ans = res;
						st = fir;
					}
				}
				for(int i = 0; i < n; i++) if(G[fir][i]) dp3[i] = max(dp3[i], dp2[fir] + 1);
			}
			
			fill(dp2, dp2 + Maxn, -Inf);
			dp2[sec] = 0;
			for(int fir = prev(sec); fir != sec; fir = prev(fir)){
				for(int bef = sec; bef != fir; bef = prev(bef)){
					if(G[bef][fir]) dp2[fir] = max(dp2[fir], dp2[bef] + 1);
				}
			}
			fill(dp3, dp3 + Maxn, -Inf);
			for(int fir = prev(sec); fir != sec; fir = prev(fir)){
				
				if((fir != prev(sec)) && (G[fir][sec])){
					res = 0;
					for(int P = prev(fir); P != sec; P = prev(P)){
						res = max(res, 1 + dp3[P] + max(dp[P][sec][1], dp[P][fir][0]) );
					}
					if(res > ans){
						ans = res;
						st = fir;
					}
				}
				for(int i = 0; i < n; i++) if(G[fir][i]) dp3[i] = max(dp3[i], dp2[fir] + 1);
			}
			
		}
	}
	
	cout << ans << '\n' << st + 1 << '\n';
	
	return 0;
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0
*/

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	3 ms	504 KB	Output is correct
5	Correct	3 ms	632 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	4 ms	632 KB	Output is correct
8	Correct	9 ms	636 KB	Output is correct
9	Correct	8 ms	760 KB	Output is correct
10	Correct	7 ms	760 KB	Output is correct
11	Correct	10 ms	760 KB	Output is correct
12	Correct	120 ms	1272 KB	Output is correct
13	Correct	292 ms	1772 KB	Output is correct
14	Correct	164 ms	2172 KB	Output is correct
15	Correct	1580 ms	2644 KB	Output is correct
16	Correct	1843 ms	2648 KB	Output is correct
17	Correct	1598 ms	2672 KB	Output is correct
18	Correct	283 ms	2680 KB	Output is correct
19	Correct	2056 ms	2756 KB	Output is correct
20	Correct	2081 ms	2632 KB	Output is correct