Submission #986783

#	Time	Username	Problem	Language	Result	Execution time	Memory
986783		vjudge1	Sailing Race (CEOI12_race)	C++17	100 / 100	378 ms	5040 KiB

race

#include<bits/stdc++.h>
using namespace std;   
#pragma GCC optimize(2)
int dp1[512][1024],dp2[512][1024];
pair<int,int>ans;
vector<int>adj[512],rev[512];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,t;
    cin>>n>>t;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        while(x){
            adj[i].push_back(x);
            rev[x].push_back(i);
            cin>>x;
        }
    }
    for(int d=2;d<=n;d++){
        for(int i=1,j;i<=n;i++){
            j=i+d;
            for(auto x:adj[(i-1)%n+1]) {
                if(i>x)x+=n; if(j<=x)continue;
                dp1[i][j]=max(dp1[i][j],1+max(dp1[x-(x>n)*n][j-(x>n)*n],dp2[i][x]));
            }
            for(auto x:adj[(j-1)%n+1]) {
                if(i>=x)x+=n; if(j<x)continue;
                dp2[i][j]=max(dp2[i][j],1+max(dp1[x-(x>n)*n][j-(x>n)*n],dp2[i][x]));
            }
        }
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,{dp1[i][i+n],i});
    if(t==0||ans.first>n-2){
        cout<<ans.first<<'\n'<<ans.second<<'\n';
        return 0;
    }
    for(int B=1;B<=n;B++){
        if(rev[B].empty())continue;
        vector<int>dis(n+1);
        for(auto i:adj[B])dis[i]=1;
        for(int C=B%n+1;C-B;C=C%n+1){
            if(!dis[C]) continue;
            for(auto j:adj[C])
                dis[j]=max(dis[j],dis[C]+1);
            auto x=upper_bound(rev[B].begin(),rev[B].end(),C);
            if(x==rev[B].end())
                x=rev[B].begin();
            if(*x<C&&C<B)break;
            if(*x>B&&C<B)break;
            if(*x<C&&B<*x)break;
            for(auto D:adj[C]) if(*x>B){if(*x<D||D<B)
                ans=max(ans,{dis[C]+2+max(dp1[D][B+(D>B)*n],dp2[*x][D+(D<B)*n]),*x});
            } else if(B>D&&D>*x)
                ans=max(ans,{dis[C]+2+max(dp2[*x][D],dp1[D][B]),*x});
        }
    }
    for(int B=1;B<=n;B++){
        if(rev[B].empty())continue;
        vector<int>dis(n+1);
        for(auto i:adj[B])dis[i]=1;
        for(int C=(B+n-2)%n+1;C-B;C=(C+n-2)%n+1){
            if(!dis[C]) continue;
            for(auto j:adj[C])
                dis[j]=max(dis[j],dis[C]+1);
            auto x=lower_bound(rev[B].begin(),rev[B].end(),C);
            if(x==rev[B].begin())
                x=--rev[B].end();
            else x--;
            if(*x>C&&C>B)break;
            if(*x<B&&C>B)break;
            if(*x>C&&B>*x)break;
            for(auto D:adj[C]) if(*x<B){if(*x>D||D>B)
                ans=max(ans,{dis[C]+2+max(dp1[D][*x+(D>*x)*n],dp2[B][D+(D<*x)*n]),*x});
            } else if(B<D&&D<*x)
                ans=max(ans,{dis[C]+2+max(dp1[D][*x],dp2[B][D]),*x});
        }
    }
    cout<<ans.first<<'\n'<<ans.second<<'\n';
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:24:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   24 |                 if(i>x)x+=n; if(j<=x)continue;
      |                 ^~
race.cpp:24:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   24 |                 if(i>x)x+=n; if(j<=x)continue;
      |                              ^~
race.cpp:28:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   28 |                 if(i>=x)x+=n; if(j<x)continue;
      |                 ^~
race.cpp:28:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   28 |                 if(i>=x)x+=n; if(j<x)continue;
      |                               ^~

• Subtask 1: 100 / 100