Submission #260692

#	Time	Username	Problem	Language	Result	Execution time	Memory
260692		georgerapeanu	Sailing Race (CEOI12_race)	C++11	100 / 100	2103 ms	5368 KiB

race

#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 forced[NMAX + 5][NMAX + 5][2];
int bst[NMAX + 5][NMAX + 5];

int graph[NMAX + 5][NMAX + 5];

bool is_in_strict(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][v] = 1;
        }
    }

    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            dp[i][j][0] = 0;
            dp[i][j][1] = 0;
            forced[i][j][0] = -2 * n * (i != j);
            forced[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(int k = nxt(i);k != j;k = nxt(k)){
                if(graph[i][k]){
                    dp[i][j][0] = max(dp[i][j][0],1 + max(dp[i][k][1],dp[k][j][0]));
                    forced[i][j][0] = max(forced[i][j][0],1 + forced[k][j][0]);
                }
            }
            if(graph[i][j]){
                forced[i][j][0] = max(forced[i][j][0],1);
            }
            for(int k = ant(j);k != i;k = ant(k)){
                if(graph[j][k]){
                    dp[i][j][1] = max(dp[i][j][1],1 + max(dp[k][j][0],dp[i][k][1]));
                    forced[i][j][1] = max(forced[i][j][1],1 + forced[i][k][1]);
                }
            }
            if(graph[j][i]){
                forced[i][j][1] = max(forced[i][j][1],1);
            }
        }
    }

    int ans = 0;
    int fst = -1;

    for(int i = 1;i <= n;i++){
        for(int k = nxt(i);k != i;k = nxt(k)){
            if(graph[i][k] == 1){
                int a = dp[i][k][1];
                int b = dp[k][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_int = -1,bst_ext = -1;
                for(int i = ant(k);i != j;i = ant(i)){
                    if(graph[i][j]){
                        bst_int = i;
                        break;
                    }
                }
                for(int i = nxt(k);i != j;i = nxt(i)){
                    if(graph[i][j]){
                        bst_ext = i;
                        break;
                    }
                }

                ///interior
                int i = bst_int;
                for(int l = nxt(j);l != k;l = nxt(l)){
                    if(graph[k][l] && i != -1 && is_in_strict(l,k,i)){
                        if(ans < 2 + forced[k][j][1] + max(dp[j][l][1],dp[l][i][0])){
                            ans = 2 + forced[k][j][1] + max(dp[j][l][1],dp[l][i][0]);
                            fst = i;
                        }
                    }
                }

                ///exterior
                i = bst_ext;
                for(int l = nxt(k);l != j;l = nxt(l)){
                    if(graph[k][l] && i != -1 && is_in_strict(k,l,i)){
                        if(ans < 2 + forced[j][k][0] + max(dp[l][j][0],dp[i][l][1])){
                            ans = 2 + forced[j][k][0] + max(dp[l][j][0],dp[i][l][1]);
                            fst = i;
                        }
                    }
                }
            }
        }
    }

    printf("%d\n%d\n",ans,fst);

    return 0;
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100