Submission #679064

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
679064	2023-01-07T11:05:11 Z	vjudge1	Sailing Race (CEOI12_race)	C++17	35 / 100	3000 ms	8252 KB

race

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;


int n, k, dp[MAXN][MAXN][2], ans;
vector<int> adj[MAXN];
bool bio[MAXN];
int cur_i, cur_j, cur_b;
int main(){
	cin >> n >> k;
	for(int i = 0; i < n; ++i){
		int x; cin >> x;
		while(x){
			--x;
			adj[x].push_back(i);
			adj[x].push_back(i + n);
			adj[x + n].push_back(i);
			adj[x + n].push_back(i + n);
			cin >> x;
		}
	}
	for(int off = 1; off < n; ++off){
		for(int i = 0; i < 2 * n - off; ++i){
			int j = i + off;
			for(int x : adj[i]){
				if(i < x && x <= j) dp[i][j][0] = max(dp[i][j][0], max(dp[i + 1][x][1], dp[x][j][0]) + 1);
			}
			for(int x : adj[j]){
				if(i <= x && x < j) dp[i][j][1] = max(dp[i][j][1], max(dp[x][j - 1][0], dp[i][x][1]) + 1);
			}
			ans = max(ans, dp[i][j][0]);
			ans = max(ans, dp[i][j][1]);
		}
	}
	for(int off = 1; off < n; ++off){
		for(int i = 0; i < 2 * n - off; ++i){
			int j = i + off;
			if(max(dp[i][j][0], dp[i][j][1]) == ans){
				cur_i = i; cur_j = j;
				if(dp[i][j][1] == ans) cur_b = 1;
				break;
			}
		}
		if(cur_i != cur_j) break;
	}
	
	while(cur_i != cur_j){
		int val = dp[cur_i][cur_j][cur_b];
		if(cur_b){
			bio[cur_j % n] = 1;
			for(int x : adj[cur_j]){
				if(cur_i <= x && x < cur_j){
					if(dp[cur_i][x][1] + 1 == val){
						cur_j = x; cur_b = 1;
						break;
					}
					if(dp[x][cur_j - 1][0] + 1 == val){
						cur_i = x; --cur_j; cur_b = 0;
						break;
					}
				}
			}
		} else {
			bio[cur_i % n] = 1;
			for(int x : adj[cur_i]){
				if(cur_i < x && x <= cur_j){
					if(dp[cur_i + 1][x][1] + 1 == val){
						++cur_i; cur_j = x; cur_b = 1;
						break;
					}
					if(dp[x][cur_j][0] + 1 == val){
						cur_i = x; cur_b = 0;
						break;
					}
				}
			}
		}
	}
	cur_i %= n;
	bio[cur_i] = 1;
	if(k){
		if(ans == n){
			cout << ans << "\n" << cur_i + 1;
		} else {
			cout << ans + 1 << "\n";
			for(int i = 0; i < n; ++i){
				if(!bio[i]){
					cout << i + 1 << "\n";
				}
			}
		}
	} else {
		cout << ans << "\n" << cur_i + 1;
	}
	return 0;
}

Subtask #1

35.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Incorrect	1 ms	468 KB	Output isn't correct
3	Incorrect	1 ms	468 KB	Output isn't correct
4	Execution timed out	3076 ms	596 KB	Time limit exceeded
5	Execution timed out	3064 ms	724 KB	Time limit exceeded
6	Execution timed out	3094 ms	852 KB	Time limit exceeded
7	Correct	3 ms	980 KB	Output is correct
8	Incorrect	2 ms	980 KB	Output isn't correct
9	Correct	5 ms	1108 KB	Output is correct
10	Correct	11 ms	1364 KB	Output is correct
11	Correct	8 ms	1236 KB	Output is correct
12	Incorrect	16 ms	2516 KB	Output isn't correct
13	Incorrect	33 ms	3920 KB	Output isn't correct
14	Correct	66 ms	5556 KB	Output is correct
15	Incorrect	202 ms	7824 KB	Output isn't correct
16	Incorrect	208 ms	8220 KB	Output isn't correct
17	Incorrect	169 ms	7748 KB	Output isn't correct
18	Correct	80 ms	7400 KB	Output is correct
19	Incorrect	223 ms	8252 KB	Output isn't correct
20	Incorrect	226 ms	8224 KB	Output isn't correct