Submission #679064

#	Time	Username	Problem	Language	Result	Execution time	Memory
679064		vjudge1	Sailing Race (CEOI12_race)	C++17	35 / 100	3094 ms	8252 KiB

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 / 100