Submission #606548

# Submission time Handle Problem Language Result Execution time Memory
606548 2022-07-26T07:08:33 Z unOrdinary Sailing Race (CEOI12_race) C++17
100 / 100
1085 ms 4636 KB
#include <bits/stdc++.h>
using namespace std;
 
const int mxN=500;
int n, ai, dp1[mxN][mxN][2], dp2[mxN][mxN][2], b[mxN][2];
bool k, adj[mxN][mxN];
array<int, 2> ans;
 
void c(int l, int r, int a) {
    if (adj[l][r]) {
        dp1[l][r][a]=1;
        dp2[l][r][a]=1+dp2[r][b[l][a]][a^1];
    } else {
        dp1[l][r][a]=dp2[l][r][a]=-n;
    }
    for(int m=b[l][a]; m!=r; m=b[m][a]) {
        dp1[l][r][a]=max(dp1[l][m][a]+dp1[m][r][a], dp1[l][r][a]); // start from l end at r
        dp2[l][r][a]=max(dp1[l][m][a]+dp2[m][r][a], dp2[l][r][a]); 
    }
    dp2[l][r][a]=max(dp2[l][r][a], dp2[l][b[r][a^1]][a]); // start form l end at most r
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("0.in", "r", stdin);
    
    cin >> n >> k;
    for(int i=0; i<n; ++i) {
        cin >> ai;
        while(ai) {
            adj[i][ai-1]=1;
            cin >> ai;
        }
        b[i][0]=(i+n-1)%n;
        b[i][1]=(i+1)%n;
    }
    for(int l=1; l<n; ++l) 
    for(int i=0; i<n; ++i) {
        c(i, (i+l)%n, 1);
        c((i+l)%n, i, 0);
    }
    for(int i=0; i<n; ++i)
    for(int j=0; j<n; ++j)
    for(int k=0; k<2; ++k)
        ans=max({{dp2[i][j][k], i}, ans});

    if(k) {
        for(int i=0; i<n; ++i) 
        for(int j=0; j<n; ++j) 
        for(int a=0; a<2; ++a) {
            if(dp1[i][j][a]<=0) continue;
            int k=b[j][a];
            for(; k!=i&&!adj[k][i]; k=b[k][a]);

            if(k!=i)
                for(int l=b[k][a]; l!=i; l=b[l][a])
                if(adj[j][l])
                    ans=max({{2+dp1[i][j][a]+max(dp2[l][b[k][a]][a^1], dp2[l][b[i][a^1]][a]), k}, ans});
        }
    }
    cout << ans[0] << "\n" << ans[1]+1;
}










# 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 468 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 720 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 5 ms 1004 KB Output is correct
9 Correct 5 ms 980 KB Output is correct
10 Correct 6 ms 1108 KB Output is correct
11 Correct 6 ms 1108 KB Output is correct
12 Correct 62 ms 2004 KB Output is correct
13 Correct 171 ms 2844 KB Output is correct
14 Correct 245 ms 3668 KB Output is correct
15 Correct 975 ms 4568 KB Output is correct
16 Correct 1050 ms 4604 KB Output is correct
17 Correct 991 ms 4568 KB Output is correct
18 Correct 422 ms 4500 KB Output is correct
19 Correct 1041 ms 4632 KB Output is correct
20 Correct 1085 ms 4636 KB Output is correct