Submission #1224349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224349		sam230609	Sailing Race (CEOI12_race)	C++20	100 / 100	814 ms	5332 KiB

race

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,q,type,edge[501][501],dp[501][501][2],dp1[501][501][2],nx[501][2]; string s;
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]=dp1[l][r][x]=-1e9;
    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]);
}
int main(){
    cin >>n>>type;
    for(int i=0,x;i<n;i++){
        while(cin >>x && x--!=0) edge[i][x]=1;
        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,make_pair(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]) st=nx[st][x];
                    if(st==l) continue;
                    for(int ed=nx[st][x];ed!=l;ed=nx[ed][x]){
                        if(edge[r][ed]){
                            int num=max(dp1[ed][nx[st][x]][x^1],dp1[ed][nx[l][x^1]][x]);
                            ans=max(ans,make_pair(1+dp[l][r][x]+1+num,st+1));
                        }
                    }
                }
    }cout <<ans.first<<"\n"<<ans.second<<"\n";
}

• Subtask 1: 100 / 100