Submission #5867

#	Time	Username	Problem	Language	Result	Execution time	Memory
5867		cki86201	Company Planning (TOKI14_company)	C++98	100 / 100	116 ms	8152 KiB

company

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

int m, n;
int p[100010], o[100010], q[100010], d[100010];
vector <int> v[100010];

int main()
{
	scanf("%d%d",&n,&m);
	int i;
	for(i=2;i<=n;i++){
		scanf("%d",p+i);
		++o[p[i]];
	}
	int *f = q, *r = q;
	for(i=1;i<=n;i++)if(!o[i])*f++ = i;
	for(i=1;i<=n;i++)d[i] = 1;
	while(f != r){
		int t = *r++;
		if(--o[p[t]] == 0)*f++ = p[t], d[p[t]] += d[t];
	}
	int L = 0, R = n, K = 0;
	while(L <= R){
		int M = (L+R) >> 1;
		for(i=0;i<n;i++){
			int u = q[i], cnt = 1;
			sort(v[u].begin(), v[u].end());
			reverse(v[u].begin(), v[u].end());
			for(int j=0;j<M && j<(int)v[u].size();j++)cnt += v[u][j];
			v[p[u]].push_back(cnt);
			if(i == n-1){
				if(cnt >= m)K = M, R = M-1;
				else L = M+1;
			}
		}
		for(i=1;i<=n;i++)v[i].clear();
	}
	printf("%d",K);
	return 0;
}

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