# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
260538 | georgerapeanu | Sailing Race (CEOI12_race) | C++11 | 609 ms | 5120 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int k;
const int NMAX = 500;
int dp[NMAX + 5][NMAX + 5][2];
int force[NMAX + 5][NMAX + 5][2];
int bst[NMAX + 5][NMAX + 5];
vector<int> graph[NMAX + 5];
vector<int> graphT[NMAX + 5];
bool is_in(int st,int dr,int pos){
if(st <= dr){
return st < pos && pos < dr;
}
return st < pos || pos < dr;
}
int nxt(int pos,int d = 1){
return (pos + d - 1) % n + 1;
}
int ant(int pos){
return nxt(pos,n - 1);
}
int dist(int i,int j){
if(j >= i){
return j - i;
}
return i + n - j;
}
int main(){
scanf("%d %d",&n,&k);
for(int i = 1;i <= n;i++){
int u = i,v = -1;
while(scanf("%d",&v) == 1){
if(v == 0){
break;
}
graph[u].push_back(v);
graphT[v].push_back(u);
}
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
dp[i][j][0] = -2 * n * (i != j);
dp[i][j][1] = -2 * n * (i != j);
force[i][j][0] = -2 * n * (i != j);
force[i][j][1] = -2 * n * (i != j);
}
}
for(int l = 1;l < n;l++){
for(int i = 1;i <= n;i++){
int j = nxt(i,l);
for(auto it:graph[i]){
if(is_in(i,j,it)){
dp[i][j][0] = max(dp[i][j][0],1 + max(dp[it][j][0],dp[nxt(i)][it][1]));
force[i][j][0] = max(force[i][j][0],1 + force[it][j][0]);
}
}
for(auto it:graph[j]){
if(is_in(i,j,it)){
dp[i][j][1] = max(dp[i][j][1],1 + max(dp[i][it][1],dp[it][ant(j)][0]));
force[i][j][1] = max(force[i][j][1],1 + force[i][it][1]);
}
}
}
}
int ans = 0;
int fst = -1;
for(int i = 1;i <= n;i++){
for(auto it:graph[i]){
int a = dp[nxt(i)][it][1];
int b = dp[it][ant(i)][0];
if(ans < 1 + max(a,b)){
ans = 1 + max(a,b);
fst = i;
}
}
}
if(k){
for(int j = 1;j <= n;j++){
for(int k = nxt(j);k != j;k = nxt(k)){
int bst_ext = -1;
int bst_int = -1;
for(auto i:graphT[j]){
if(is_in(j,k,i) == false){
if(bst_ext == -1 || dist(k,i) < dist(k,bst_ext)){
bst_ext = i;
}
}
else{
if(bst_int == -1 || dist(i,k) < dist(bst_int,k)){
bst_int = i;
}
}
}
for(auto l:graph[k]){
if(is_in(j,k,l) == false){
if(bst_ext != -1 && is_in(k,l,bst_ext)){
int a = dp[l][ant(j)][0];
int b = dp[nxt(bst_ext)][l][1];
if(ans < 2 + max(a,b) + force[j][k][0]){
ans = 2 + max(a,b) + force[j][k][0];
//printf("%d %d %d %d and %d %d %d\n",j,k,l,bst_ext,force[j][k][0],a,b);
fst = bst_ext;
}
}
}
else{
if(bst_int != -1 && is_in(l,k,bst_int)){
int a = dp[nxt(j)][l][1];
int b = dp[l][ant(bst_int)][0];
if(ans < 2 + max(a,b) + force[k][j][1]){
ans = 2 + max(a,b) + force[k][j][1];
//printf("%d %d %d %d and %d %d %d\n",j,k,l,bst_int,force[k][j][1],a,b);
fst = bst_int;
}
}
}
}
}
}
}
printf("%d\n%d\n",ans,fst);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |