Submission #1177602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177602		Godgift42	Sailing Race (CEOI12_race)	C++20	0 / 100	3095 ms	2368 KiB

race

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    vector<vector<int>> adj(n,vector<int>(n));
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        while(x!=0){
            x--;
            adj[i][x]=1;
            cin >> x;
        }
    }
    vector<vector<int>> dp(n,vector<int>(n));
    pair<int,int> ans={-1,-1};
    for(int i=1;i<n;i++){
        for(int j=0;j<n;j++){
            int r=(j+i)%n;
            int ma1=0;
            int ma2=0;
            if(j<r){
                for(int o=j+1;o<r;o++){
                    if(adj[r][o]){
                        ma1=max(ma1,max(dp[o][j]-adj[o][j],dp[o][r]-adj[o][r])+1);
                    }
                    if(adj[j][o]){
                        ma2=max(ma2,max(dp[o][j]-adj[o][j],dp[o][r]-adj[o][r])+1);
                    }
                }
            }
            else{
                for(int o=j+1;o<r+n;o++){
                    o%=n;
                    if(adj[r][o]){
                        ma1=max(ma1,max(dp[o][j]-adj[o][j],dp[o][r]-adj[o][r])+1);
                    }
                    if(adj[j][o]){
                        ma2=max(ma2,max(dp[o][j]-adj[o][j],dp[o][r]-adj[o][r])+1);
                    }
                }
            }
            if(adj[j][r]){
                dp[j][r]=max(ma1+adj[j][r],dp[j][r]);
                if(ans.first<dp[j][r])ans={dp[j][r],r};
            }
            if(adj[r][j]){
                dp[r][j]=max(ma2+adj[r][j],dp[j][r]);
                if(ans.first<dp[r][j])ans={dp[r][j],r};
            }
        }
    }
    if(k==0){
        cout << ans.first << " " << ans.second <<"\n";
    }
}

• Subtask 1: 0 / 100