Submission #13855

#	Time	Username	Problem	Language	Result	Execution time	Memory
13855		gs14004	Company Planning (TOKI14_company)	C++14	100 / 100	344 ms	14276 KiB

company

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> graph[100005];
int n,m;
int lim;

int solve(int x){
    vector<int> ret;
    for (int i=0; i<graph[x].size(); i++) {
        ret.push_back(solve(graph[x][i]));
    }
    sort(ret.begin(),ret.end());
    reverse(ret.begin(),ret.end());
    int res = 0;
    for (int i=0; i<lim && i < ret.size(); i++) {
        res += ret[i];
    }
    return res + 1;
}

bool trial(int x){
    lim = x;
    return solve(1) >= m;
}

int main(){
    scanf("%d %d",&n,&m);
    for (int i=2; i<=n; i++) {
        int t;
        scanf("%d",&t);
        graph[t].push_back(i);
    }
    int s = 0, e = n;
    while (s != e) {
        int m = (s+e)/2;
        if(trial(m)) e = m;
        else s = m+1;
    }
    printf("%d",s);
}

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