Submission #265339

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
265339	2020-08-14T16:07:02 Z	TadijaSebez	Sailing Race (CEOI12_race)	C++11	100 / 100	1063 ms	6268 KB

race

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
void ckmx(int&x,int y){x=max(x,y);}
const int N=505;
vector<int> E[N];
int dp[N][N][2],n,k,tmp[N];
bool was[N][N][2];
int on(int l,int r,int v){
	return (l<=r&&l<=v&&r>=v)||(l>r&&(v<=r||v>=l));
}
int DP(int l,int r,int side){
	if(was[l][r][side])return dp[l][r][side];
	int u=side==0?l:r;
	was[l][r][side]=1;
	int L=side==0?(l==n?1:l+1):l;
	int R=side==1?(r==1?n:r-1):r;
	for(int v:E[u]){
		if(on(l,r,v)){
			ckmx(dp[l][r][side],1+max(DP(L,v,1),DP(v,R,0)));
		}
	}
	return dp[l][r][side];
}
int go[N][N][2],has[N][N];
int main(){
	scanf("%i %i",&n,&k);
	for(int i=1;i<=n;i++){
		while(1){
			int j;
			scanf("%i",&j);
			if(j==0)break;
			E[i].pb(j);
			has[i][j]=1;
		}
	}
	auto nxt=[&](int x){return x==n?1:x+1;};
	auto pre=[&](int x){return x==1?n:x-1;};
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)tmp[j]=-N;
		tmp[i]=0;
		for(int j=i;;j=nxt(j)){
			go[i][j][0]=tmp[j];
			for(int r:E[j]){
				ckmx(tmp[r],tmp[j]+1);
			}
			if(j==pre(i))break;
		}
		for(int j=1;j<=n;j++)tmp[j]=-N;
		tmp[i]=0;
		for(int j=i;;j=pre(j)){
			go[i][j][1]=tmp[j];
			for(int r:E[j]){
				ckmx(tmp[r],tmp[j]+1);
			}
			if(j==nxt(i))break;
		}
	}
	int ans=-1,idx=0;
	for(int i=1;i<=n;i++){
		int now=DP(i,i==1?n:i-1,0);
		if(now>ans)ans=now,idx=i;
	}
	if(k==1){
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j){
			if(go[i][j][0]!=0){
				int r=-1;
				for(int l=nxt(j);l!=i;l=nxt(l))if(has[l][i]){r=l;break;}
				if(r!=-1){
					for(int z=nxt(r);z!=i;z=nxt(z))if(has[j][z]){
						int now=1+go[i][j][0]+1+max(DP(nxt(r),z,1),DP(z,pre(i),0));
						if(ans<now)ans=now,idx=r;
					}
				}
			}
			if(go[i][j][1]!=0){
				int r=-1;
				for(int l=pre(j);l!=i;l=pre(l))if(has[l][i]){r=l;break;}
				if(r!=-1){
					for(int z=pre(r);z!=i;z=pre(z))if(has[j][z]){
						int now=1+go[i][j][1]+1+max(DP(z,pre(r),0),DP(nxt(i),z,1));
						if(ans<now)ans=now,idx=r;
					}
				}
			}
		}
	}
	printf("%i\n%i\n",ans,idx);
	return 0;
}

Compilation message

race.cpp: In function 'int main()':
race.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |  scanf("%i %i",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~~
race.cpp:31:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |    scanf("%i",&j);
      |    ~~~~~^~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	1 ms	640 KB	Output is correct
4	Correct	2 ms	768 KB	Output is correct
5	Correct	2 ms	896 KB	Output is correct
6	Correct	3 ms	1056 KB	Output is correct
7	Correct	6 ms	1152 KB	Output is correct
8	Correct	5 ms	1280 KB	Output is correct
9	Correct	10 ms	1408 KB	Output is correct
10	Correct	22 ms	1536 KB	Output is correct
11	Correct	11 ms	1536 KB	Output is correct
12	Correct	64 ms	2552 KB	Output is correct
13	Correct	139 ms	3728 KB	Output is correct
14	Correct	95 ms	4832 KB	Output is correct
15	Correct	735 ms	6092 KB	Output is correct
16	Correct	928 ms	6220 KB	Output is correct
17	Correct	753 ms	6092 KB	Output is correct
18	Correct	115 ms	5880 KB	Output is correct
19	Correct	1055 ms	6268 KB	Output is correct
20	Correct	1063 ms	6268 KB	Output is correct