Submission #606548

#	Time	Username	Problem	Language	Result	Execution time	Memory
606548		unOrdinary	Sailing Race (CEOI12_race)	C++17	100 / 100	1085 ms	4636 KiB

race

#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;
}

• Subtask 1: 100 / 100