Submission #375430

#	Time	Username	Problem	Language	Result	Execution time	Memory
375430		YJU	Sailing Race (CEOI12_race)	C++14	40 / 100	2329 ms	8540 KiB

race

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=5e2+5;
const ll MOD=1e9+7;
const ll INF=(1<<28);
const ld pi=acos(-1);
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,n) for(int i=1;i<=n;++i)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,type,x,dp[N][N][2];
ll dis[N][N],rdis[N][N];
bitset<N> grid[N];
ll nxt_edge[N][N],lst_edge[N][N];

ll ansm,anss;

void upd(ll ans,ll id){
	if(ans>=ansm){
		ansm=ans,anss=id;
	}
}

bool in(ll id,ll l,ll r){
	if(r<l){
		return (id<=r||id>=l);
	}else{
		return (l<=id&&id<=r);
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>type;
	REP(i,n){
		while(1){
            cin>>x;
            if(x==0)break;
            grid[i][x-1]=1;
		}
	}
	for(int len=2;len<n;len++){
        for(int i=0,j=(i+len>=n?i+len-n:i+len);i<n;i++,j=(j+1>=n?0:j+1)){
            for(int k=(i+1>=n?0:i+1);k!=j;k=(k+1>=n?0:k+1)){
				//i,j,0 means boat is now at i
				//i,j,1,means boat is now at j
                dp[i][j][0]=max(dp[i][j][0],(grid[i][k]?1+max(dp[i][k][1],dp[k][j][0]):0));
                dp[i][j][1]=max(dp[i][j][1],(grid[j][k]?1+max(dp[i][k][1],dp[k][j][0]):0));
            }
        }
	}
	//no cross
	REP(i,n)REP(j,n){
		if(i==j)continue;
		if(grid[i][j])upd(max(dp[i][j][1],dp[j][i][0])+1,i);
	}
	if(type==0){cout<<ansm<<"\n"<<anss+1<<"\n";return 0;}
	//
	REP(i,N)REP(j,N)dis[i][j]=rdis[i][j]=-INF;
    //type==1
    for(int i=0;i<n;i++){
		dis[i][i]=rdis[i][i]=0;
        for(int j=i;;j=(j+1>=n?0:j+1)){
            for(int k=0;k<n;k++){
				if(grid[j][k]==0)continue;
				if(in(k,i,j))continue;
				dis[i][k]=max(dis[i][k],dis[i][j]+1);
            }
            if((j+1>=n?0:j+1)==i)break;
        }
        for(int j=i;;j=(j-1==-1?n-1:j-1)){
			for(int k=0;k<n;k++){
				if(grid[j][k]==0)continue;
				if(in(k,j,i))continue;
				rdis[i][k]=max(rdis[i][k],rdis[i][j]+1);
			}
			if((j-1==-1?n-1:j-1)==i)break;
        }
        /*
        */
    }
    REP(i,N)REP(j,N)nxt_edge[i][j]=lst_edge[i][j]=-1;

	for(int i=0;i<n;i++){
		for(int j=i;;j=(j-1==-1?n-1:j-1)){
			nxt_edge[i][j]=nxt_edge[i][(j+1>=n?0:j+1)];
			if(i==j)nxt_edge[i][j]=-1;
			if(grid[j][i])nxt_edge[i][j]=j;
			if((j-1==-1?n-1:j-1)==i)break;
		}
		for(int j=i;;j=(j+1>=n?0:j+1)){
			lst_edge[i][j]=lst_edge[i][(j-1==-1?n-1:j-1)];
			if(i==j)lst_edge[i][j]=-1;
			if(grid[j][i])lst_edge[i][j]=j;
			if((j+1>=n?0:j+1)==i)break;
		}
		cout<<"ND="<<i<<"\n";
		REP(j,n)cout<<nxt_edge[i][j]<<" \n"[j==n-1];
		REP(j,n)cout<<lst_edge[i][j]<<" \n"[j==n-1];
	}
    for(ll b=0;b<n;b++){
		for(ll c=0;c<n;c++){
			if(b==c)continue;
            ll a=nxt_edge[b][(c+1==n?0:c+1)];
            for(ll d=0;d<n;d++){
				if(d==a||d==b||d==c||a==-1||a==b||a==c)continue;
                if(grid[c][d]&&in(d,a,b)){
					ll val=1+dis[b][c]+1+max(dp[a][d][1],dp[d][b][0]);
					upd(val,a);
                }
            }
            a=lst_edge[b][(c-1==-1?n-1:c-1)];
            for(ll d=0;d<n;d++){
				if(d==a||d==b||d==c||a==-1||a==b||a==c)continue;
				if(grid[c][d]&&in(d,b,a)){
                    ll val=1+rdis[b][c]+1+max(dp[b][d][1],dp[d][a][0]);
                    upd(val,a);
				}
            }
		}
    }
    cout<<ansm<<"\n"<<anss+1<<"\n";
	return 0;
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0


*/

• Subtask 1: 40 / 100