Submission #132260

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
132260	2019-07-18T15:26:12 Z	amoo_safar	Sailing Race (CEOI12_race)	C++14	55 / 100	3000 ms	2556 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)){
					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)){
					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

55.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	Incorrect	3 ms	504 KB	Output isn't correct
4	Correct	5 ms	504 KB	Output is correct
5	Correct	4 ms	632 KB	Output is correct
6	Incorrect	13 ms	632 KB	Output isn't correct
7	Correct	8 ms	632 KB	Output is correct
8	Incorrect	25 ms	760 KB	Output isn't correct
9	Correct	14 ms	760 KB	Output is correct
10	Correct	16 ms	760 KB	Output is correct
11	Correct	20 ms	760 KB	Output is correct
12	Correct	376 ms	1300 KB	Output is correct
13	Incorrect	1152 ms	1656 KB	Output isn't correct
14	Correct	821 ms	2224 KB	Output is correct
15	Execution timed out	3045 ms	2552 KB	Time limit exceeded
16	Execution timed out	3034 ms	2552 KB	Time limit exceeded
17	Execution timed out	3067 ms	2556 KB	Time limit exceeded
18	Correct	1578 ms	2556 KB	Output is correct
19	Execution timed out	3061 ms	2552 KB	Time limit exceeded
20	Execution timed out	3033 ms	2552 KB	Time limit exceeded