Submission #787994

#	Time	Username	Problem	Language	Result	Execution time	Memory
787994		nonono	Sailing Race (CEOI12_race)	C++14	100 / 100	912 ms	5268 KiB

race

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e8;
const int mxN = 505;
int n, type;
int edge[mxN][mxN];
int d[mxN][2];

int f[mxN][mxN][2];
int dp[mxN][mxN][2];

void dq(int i, int j, int k) {
    if(edge[i][j]) {
        f[i][j][k] = 1;
        dp[i][j][k] = dp[j][d[i][k]][k ^ 1] + 1; 
    } else {
        f[i][j][k] = - inf;
        dp[i][j][k] = - inf;
    }
    
    for(int l = d[i][k]; l != j; l = d[l][k]) {
        f[i][j][k] = max(f[i][j][k], f[i][l][k] + f[l][j][k]);
        dp[i][j][k] = max(dp[i][j][k], f[i][l][k] + dp[l][j][k]);
    }
    
    dp[i][j][k] = max(dp[i][j][k], dp[i][d[j][k ^ 1]][k]);
}

signed main() {
    
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    
    cin >> n >> type;
    
    for(int i = 1; i <= n; i ++) {
        int v;
        while(cin >> v) {
            if(!v) break ;
            edge[i][v] = 1;
        }
    
        d[i][0] = i % n + 1;
        d[i][1] = (i > 1 ? i - 1 : n);
    }
    
    for(int k = 2; k <= n; k ++) {
        for(int i = 1; i <= n; i ++) {
            int j = (i + k - 1 - 1) % n + 1;
            
            dq(i, j, 0);
            dq(j, i, 1);
        }
    }
    
    pair<int, int> result = {0, 0};
    
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++) {
            for(int k : {0, 1}) {
                if(dp[i][j][k] > result.first) {
                    result = {dp[i][j][k], i};
                }
            }
        } 
    }
    
    if(type) {
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= n; j ++) {
                for(int k : {0, 1}) {
                    if(f[i][j][k] <= 0) continue ;
                    
                    int S = d[j][k];
                    while(S != i && !edge[S][i]) S = d[S][k];
                    if(S == i) continue ;
                    
                    for(int T = d[S][k]; T != i; T = d[T][k]) {
                        if(edge[j][T]) {
                            int x = max(dp[T][d[i][k ^ 1]][k], dp[T][d[S][k]][k ^ 1]);
                            if(x + f[i][j][k] + 2 > result.first) {
                                result = {x + f[i][j][k] + 2, S};
                            }
                        }
                    }
                }
            }
        }
    }
    
    cout << result.first << "\n";
    cout << result.second << "\n";
    return 0;
}

• Subtask 1: 100 / 100