Submission #1146617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146617		mnbvcxz123	Sailing Race (CEOI12_race)	C++20	100 / 100	853 ms	6584 KiB

race

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
using namespace std;

constexpr int N = 501;
bool adj[N][N];
pair<int, int> ans;
int dp[N][N][2], dp1[N][N][2], dp2[N][N][2], nx[N][2];
 
void calc(int u, int v, int dir){
	if (adj[u][v]){
		dp[u][v][dir] = 1;
		dp1[u][v][dir] = 1+dp2[v][nx[u][dir]][dir^1];
	} else {
		dp[u][v][dir] = dp1[u][v][dir] = -N;
	}
	for (int k = nx[u][dir]; k != v; k = nx[k][dir]){
		dp[u][v][dir] = max(dp[u][v][dir], dp[u][k][dir] + dp[k][v][dir]);
		dp1[u][v][dir] = max(dp1[u][v][dir], dp[u][k][dir] + dp1[k][v][dir]);
	}
	dp2[u][v][dir] = max(dp1[u][v][dir], dp2[u][nx[v][dir^1]][dir]);
}
 
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, cross;
	cin >> n >> cross;
	memset(adj, 0, sizeof adj);
	for (int i = 0; i < n; i++){
		int t;
		cin >> t;
		while (t!=0){
			adj[i][t-1] = true;
			cin >> t;
		}
		nx[i][0] = (i+1)%n;
		nx[i][1] = (i-1+n)%n;
		
	}
	for(int l=1;l<n;l++)
        for(int i=0;i<n;i++)
            calc(i,(i+l)%n,0),calc((i+l)%n,i,1);
	for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            for(int a=0;a<2;a++)
                ans=max(ans,make_pair(dp1[i][j][a],i));
	if (cross){
		for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                for(int a=0;a<2;a++)
                    if(dp[i][j][a]>0)
                    {
                        int k=nx[j][a];
                        for(;k!=i;k=nx[k][a])
                            if(adj[k][i])
                                break;
                        if(k!=i)
                            for(int l=nx[k][a];l!=i;l=nx[l][a])
                                if(adj[j][l])
                                    ans=max(ans,make_pair(max(dp2[l][nx[i][a^1]][a],dp2[l][nx[k][a]][a^1])+dp[i][j][a]+2,k));
                    }
	}
    cout << ans.ff << '\n' << ans.ss+1;
}

• Subtask 1: 100 / 100