Submission #787994

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
787994	2023-07-19T15:54:53 Z	nonono	Sailing Race (CEOI12_race)	C++14	100 / 100	912 ms	5268 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	1 ms	724 KB	Output is correct
5	Correct	1 ms	724 KB	Output is correct
6	Correct	2 ms	852 KB	Output is correct
7	Correct	2 ms	980 KB	Output is correct
8	Correct	4 ms	1108 KB	Output is correct
9	Correct	3 ms	1108 KB	Output is correct
10	Correct	4 ms	1236 KB	Output is correct
11	Correct	4 ms	1236 KB	Output is correct
12	Correct	54 ms	2300 KB	Output is correct
13	Correct	159 ms	3284 KB	Output is correct
14	Correct	209 ms	4280 KB	Output is correct
15	Correct	806 ms	5260 KB	Output is correct
16	Correct	846 ms	5260 KB	Output is correct
17	Correct	803 ms	5268 KB	Output is correct
18	Correct	384 ms	5260 KB	Output is correct
19	Correct	912 ms	5268 KB	Output is correct
20	Correct	880 ms	5204 KB	Output is correct