Submission #531664

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531664	2022-03-01T08:38:25 Z	Koosha_mv	Sailing Race (CEOI12_race)	C++14	50 / 100	261 ms	2720 KB

race

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=505;

int n,k,ans,a[N],deg[N],dp[N][N],pd[N][N];
vector<int> vec,g[N];

void calcdp(int u,int x){
	for(auto v : g[u]){
		int dist=(v-u+n)%n;
		if(dist<=x){
			maxm(dp[u][x],dp[v][x-dist]+1);
			maxm(dp[u][x],pd[v][dist-1]+1);
		}
	}
	maxm(ans,dp[u][x]+(k==1 && deg[u]));
}
void calcpd(int u,int x){
	for(auto v : g[u]){
		int dist=(u-v+n)%n;
		if(dist<=x){
			maxm(pd[u][x],pd[v][x-dist]+1);
			maxm(pd[u][x],dp[v][dist-1]+1);
		}
	}
	maxm(ans,pd[u][x]+(k==1 && deg[u]));
}

int main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>k;
	f(i,0,n){
		int x;
		cin>>x;
		while(x>0){
			deg[x-1]=1;
			g[i].pb(x-1);
			cin>>x;
		}
	}
	f(t,1,n){
		f(i,0,n){
			calcdp(i,t);
			calcpd(i,t);
		}
	}
	int res=-1;
	if(k==0){
		f(i,0,n) if(dp[i][n-1]==ans || pd[i][n-1]==ans) res=i+1;
	}
	else{
		f(i,0,n){
			if(dp[i][n-1]+(deg[i]>0)==ans || pd[i][n-1]+(deg[i]>0)==ans){
				if(deg[i]==0){
					res=i+1;
				}
				else{
					f(j,0,n){
						for(auto v : g[j]){
							if(v==i){
								res=j+1;
							}
						}
					}
				}
				break;
			}
		}
	}
	if(res==-1) assert(0);
	cout<<ans<<endl<<res;
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0
*/

Subtask #1

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Incorrect	1 ms	332 KB	Output isn't correct
4	Correct	1 ms	456 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Incorrect	1 ms	460 KB	Output isn't correct
7	Correct	5 ms	716 KB	Output is correct
8	Incorrect	2 ms	584 KB	Output isn't correct
9	Correct	4 ms	720 KB	Output is correct
10	Correct	11 ms	820 KB	Output is correct
11	Correct	6 ms	716 KB	Output is correct
12	Incorrect	15 ms	1100 KB	Output isn't correct
13	Incorrect	28 ms	1484 KB	Output isn't correct
14	Correct	48 ms	1920 KB	Output is correct
15	Incorrect	173 ms	2548 KB	Output isn't correct
16	Incorrect	206 ms	2672 KB	Output isn't correct
17	Incorrect	159 ms	2500 KB	Output isn't correct
18	Correct	66 ms	2388 KB	Output is correct
19	Incorrect	261 ms	2716 KB	Output isn't correct
20	Incorrect	257 ms	2720 KB	Output isn't correct