Submission #787975

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
787975	2023-07-19T15:40:39 Z	nonono	Sailing Race (CEOI12_race)	C++14	5 / 100	893 ms	5436 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], dp[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 << " " << result.second << "\n";
    return 0;
}

Subtask #1

5.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	340 KB	Output isn't correct
2	Incorrect	1 ms	468 KB	Output isn't correct
3	Incorrect	1 ms	596 KB	Output isn't correct
4	Incorrect	1 ms	716 KB	Output isn't correct
5	Incorrect	1 ms	724 KB	Output isn't correct
6	Incorrect	2 ms	852 KB	Output isn't correct
7	Incorrect	2 ms	980 KB	Output isn't correct
8	Incorrect	4 ms	1108 KB	Output isn't correct
9	Incorrect	4 ms	1328 KB	Output isn't correct
10	Correct	5 ms	1368 KB	Output is correct
11	Incorrect	4 ms	1236 KB	Output isn't correct
12	Incorrect	54 ms	2324 KB	Output isn't correct
13	Incorrect	173 ms	3312 KB	Output isn't correct
14	Incorrect	215 ms	4320 KB	Output isn't correct
15	Incorrect	829 ms	5372 KB	Output isn't correct
16	Incorrect	840 ms	5404 KB	Output isn't correct
17	Incorrect	811 ms	5332 KB	Output isn't correct
18	Incorrect	394 ms	5300 KB	Output isn't correct
19	Incorrect	893 ms	5428 KB	Output isn't correct
20	Incorrect	886 ms	5436 KB	Output isn't correct