Submission #265323

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
265323	2020-08-14T15:52:15 Z	TadijaSebez	Sailing Race (CEOI12_race)	C++11	90 / 100	1046 ms	6496 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]=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]=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

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 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	1024 KB	Output is correct
7	Correct	6 ms	1152 KB	Output is correct
8	Correct	5 ms	1280 KB	Output is correct
9	Correct	7 ms	1408 KB	Output is correct
10	Correct	21 ms	1536 KB	Output is correct
11	Correct	11 ms	1536 KB	Output is correct
12	Correct	59 ms	2560 KB	Output is correct
13	Correct	125 ms	3832 KB	Output is correct
14	Correct	92 ms	4856 KB	Output is correct
15	Correct	701 ms	6216 KB	Output is correct
16	Correct	855 ms	6136 KB	Output is correct
17	Incorrect	717 ms	6092 KB	Output isn't correct
18	Correct	114 ms	6008 KB	Output is correct
19	Correct	1046 ms	6496 KB	Output is correct
20	Incorrect	1024 ms	6424 KB	Output isn't correct