oj.uz

답안 #531664

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
531664 2022-03-01T08:38:25 Z Koosha_mv Sailing Race (CEOI12_race) C++14
50 / 100
 261 ms 2720 KB 
#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

# 결과 실행 시간 메모리 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