Submission #132262

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
132262	2019-07-18T15:30:51 Z	amoo_safar	Sailing Race (CEOI12_race)	C++14	75 / 100	3000 ms	2680 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 + 1) % n;
}
int prev(int y){
	return (y - 1 + n) % n;
}


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

75.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	508 KB	Output is correct
3	Correct	4 ms	504 KB	Output is correct
4	Correct	5 ms	504 KB	Output is correct
5	Correct	4 ms	632 KB	Output is correct
6	Correct	12 ms	632 KB	Output is correct
7	Correct	8 ms	632 KB	Output is correct
8	Correct	21 ms	760 KB	Output is correct
9	Correct	15 ms	760 KB	Output is correct
10	Correct	17 ms	760 KB	Output is correct
11	Correct	20 ms	760 KB	Output is correct
12	Correct	287 ms	1288 KB	Output is correct
13	Correct	845 ms	1784 KB	Output is correct
14	Correct	821 ms	2268 KB	Output is correct
15	Execution timed out	3050 ms	2552 KB	Time limit exceeded
16	Execution timed out	3048 ms	2556 KB	Time limit exceeded
17	Execution timed out	3035 ms	2552 KB	Time limit exceeded
18	Correct	1578 ms	2680 KB	Output is correct
19	Execution timed out	3055 ms	2552 KB	Time limit exceeded
20	Execution timed out	3033 ms	2552 KB	Time limit exceeded