oj.uz

Submission #375431

# Submission time Handle Problem Language Result Execution time Memory
375431 2021-03-09T11:33:28 Z YJU Sailing Race (CEOI12_race) C++14
100 / 100
 2312 ms 6516 KB 
#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;
		}
	}
    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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 4460 KB Output is correct
3 Correct 3 ms 4460 KB Output is correct
4 Correct 4 ms 4460 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 7 ms 4588 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 11 ms 4588 KB Output is correct
9 Correct 5 ms 748 KB Output is correct
10 Correct 4 ms 876 KB Output is correct
11 Correct 8 ms 748 KB Output is correct
12 Correct 139 ms 5100 KB Output is correct
13 Correct 351 ms 5488 KB Output is correct
14 Correct 147 ms 1900 KB Output is correct
15 Correct 1782 ms 6400 KB Output is correct
16 Correct 2065 ms 6508 KB Output is correct
17 Correct 1837 ms 6516 KB Output is correct
18 Correct 253 ms 2540 KB Output is correct
19 Correct 2282 ms 6456 KB Output is correct
20 Correct 2312 ms 6456 KB Output is correct