Submission #998593

#	Time	Username	Problem	Language	Result	Execution time	Memory
998593		doducanh	Sailing Race (CEOI12_race)	C++14	100 / 100	850 ms	5572 KiB

race

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
int edge[505][505];
int dp[505][505][2];
int dp1[505][505][2];
int nx[505][2];
int n,type;
void solve(int l,int r,int x)
{
    if(edge[l][r]){
        dp[l][r][x]=1;
        dp1[l][r][x]=1+dp1[r][nx[l][x]][x^1];
    }
    else{
        dp[l][r][x]=-n;
        dp1[l][r][x]=-n;
    }
    for(int m=nx[l][x];m!=r;m=nx[m][x]){
        dp[l][r][x]=max(dp[l][r][x],dp[l][m][x]+dp[m][r][x]);
        dp1[l][r][x]=max(dp1[l][r][x],dp[l][m][x]+dp1[m][r][x]);
    }
    dp1[l][r][x]=max(dp1[l][r][x],dp1[l][nx[r][x^1]][x]);
}
main()
{
    cin>>n>>type;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        while(x!=0){
            edge[i][x-1]=1;
            cin>>x;
        }
        nx[i][0]=(i+1)%n;
        nx[i][1]=(i+n-1)%n;
    }
    for(int d=1;d<n;d++){
        for(int l=0,r=(l+d)%n;l<n;l++,r=nx[r][0]){
            solve(l,r,0);
            solve(r,l,1);
        }
    }
    pair<int,int>ans={-1,0};
    for(int l=0;l<n;l++){
        for(int r=0;r<n;r++){
            for(int x=0;x<2;x++){
                ans=max(ans,{dp1[l][r][x],l+1});
            }
        }
    }
    if(type){
        for(int l=0;l<n;l++){
            for(int r=0;r<n;r++){
                for(int x=0;x<2;x++){
                    if(dp[l][r][x]<=0)continue;
                    int st=nx[r][x];
                    while(st!=l&&edge[st][l]==0)st=nx[st][x];
                    if(st==l)continue;
                    for(int ed=nx[st][x];ed!=l;ed=nx[ed][x]){
                        if(edge[r][ed]){
                            ans=max(ans,make_pair(max(dp1[ed][nx[l][x^1]][x],dp1[ed][nx[st][x]][x^1])+1+1+dp[l][r][x],st+1));
                        }
                    }
                }
            }
        }
    }
    cout<<ans.fi<<"\n"<<ans.se;
}

Compilation message (stderr)

race.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main()
      | ^~~~

• Subtask 1: 100 / 100