oj.uz

Submission #375430

# Submission time Handle Problem Language Result Execution time Memory
375430 2021-03-09T11:32:47 Z YJU Sailing Race (CEOI12_race) C++14
40 / 100
 2329 ms 8540 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;
		}
		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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 3 ms 4460 KB Expected integer, but "ND=0" found
3 Incorrect 4 ms 4460 KB Expected integer, but "ND=0" found
4 Incorrect 5 ms 4460 KB Expected integer, but "ND=0" found
5 Correct 2 ms 492 KB Output is correct
6 Incorrect 8 ms 4588 KB Expected integer, but "ND=0" found
7 Correct 3 ms 620 KB Output is correct
8 Incorrect 12 ms 4716 KB Expected integer, but "ND=0" found
9 Correct 5 ms 748 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Correct 7 ms 748 KB Output is correct
12 Incorrect 147 ms 5484 KB Expected integer, but "ND=0" found
13 Incorrect 357 ms 6252 KB Expected integer, but "ND=0" found
14 Correct 132 ms 2156 KB Output is correct
15 Incorrect 1815 ms 8540 KB Expected integer, but "ND=0" found
16 Incorrect 2085 ms 8428 KB Expected integer, but "ND=0" found
17 Incorrect 1849 ms 8428 KB Expected integer, but "ND=0" found
18 Correct 227 ms 2412 KB Output is correct
19 Incorrect 2317 ms 8428 KB Expected integer, but "ND=0" found
20 Incorrect 2329 ms 8532 KB Expected integer, but "ND=0" found