Submission #18505

#	Time	Username	Problem	Language	Result	Execution time	Memory
18505		suhgyuho_william	Company Planning (TOKI14_company)	C++98	100 / 100	356 ms	14276 KiB

company

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N,M,K;
vector<int> edge[100002];

int dfs(int x){
	int i,v,sum;
	priority_queue<int> q;

	for(i=0; i<edge[x].size(); i++){
		v = edge[x][i];
		q.push(dfs(v));
	}
	i = K;
	sum = 1;
	while(i > 0 && !q.empty()){
		sum += q.top();
		q.pop();
		i--;
	}
	return sum;
}

bool checking(){
	if(dfs(1) >= M) return true;
	return false;
}

int main(){
	int i,ans;
	int l,mid,r;
	//freopen("input.txt","r",stdin);

	scanf("%d %d",&N,&M);
	for(i=1; i<N; i++){
		scanf("%d",&ans);
		edge[ans].push_back(i+1);
	}
	l = 0; r = N-1;
	while(l <= r){
		mid = (l+r)/2;
		K = mid;
		if(checking()){
			ans = mid;
			r = mid-1;
		}else l = mid+1;
	}
	printf("%d",ans);

	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 20 / 20
• Subtask 3: 18 / 18
• Subtask 4: 7 / 7
• Subtask 5: 43 / 43