Submission #14204

#	Time	Username	Problem	Language	Result	Execution time	Memory
14204		ainta	Company Planning (TOKI14_company)	C++98	7 / 100	130 ms	13920 KiB

company

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>E[101000];
int n, m, D[101000], K, C[101000], w[101000];
void DFS(int a){
	int i, r = 0;
	C[a] = 1;
	for (i = 0; i < E[a].size(); i++){
		DFS(E[a][i]);
		C[a] += C[E[a][i]];
		w[i] = C[E[a][i]] - D[E[a][i]];
		r += D[E[a][i]];
	}
	if (E[a].size() <= K){
		D[a] = r;
		return;
	}
	sort(w, w + E[a].size());
	for (i = 0; i < E[a].size() - K; i++){
		r += w[i];
	}
	D[a] = r;
}
int main(){
	scanf("%d%d", &n, &m);
	int i, a, be = 0, ed = n - 1, r;
	for (i = 2; i <= n; i++){
		scanf("%d", &a);
		E[a].push_back(i);
	}
	while (be <= ed){
		K = (be + ed) >> 1;
		DFS(1);
		if (n - D[1] >= m){
			r = K;
			ed = K - 1;
		}
		else be = K + 1;
	}
	printf("%d\n", r);
}

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