Submission #531617

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531617	2022-03-01T06:48:30 Z	Koosha_mv	Sailing Race (CEOI12_race)	C++14	50 / 100	268 ms	2552 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]));
	//cout<<"dp "<<u<<" "<<x<<" -> "<<dp[u][x]<<endl;
}
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]));
	//cout<<"pd "<<u<<" "<<x<<" -> "<<pd[u][x]<<endl;
}

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=0;
	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;
			}
		}
	}
	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	0 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	460 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	3 ms	588 KB	Output is correct
8	Incorrect	1 ms	588 KB	Output isn't correct
9	Correct	4 ms	708 KB	Output is correct
10	Correct	11 ms	716 KB	Output is correct
11	Correct	6 ms	764 KB	Output is correct
12	Incorrect	16 ms	1100 KB	Output isn't correct
13	Incorrect	28 ms	1560 KB	Output isn't correct
14	Correct	52 ms	1964 KB	Output is correct
15	Incorrect	192 ms	2444 KB	Output isn't correct
16	Incorrect	208 ms	2552 KB	Output isn't correct
17	Incorrect	175 ms	2408 KB	Output isn't correct
18	Correct	77 ms	2252 KB	Output is correct
19	Incorrect	268 ms	2552 KB	Output isn't correct
20	Incorrect	257 ms	2548 KB	Output isn't correct