Submission #18497

#	Time	Username	Problem	Language	Result	Execution time	Memory
18497		eaststar	Company Planning (TOKI14_company)	C++14	0 / 100	165 ms	3792 KiB

company

#include <stdio.h>
#include <queue>
using namespace std;
struct al{
    int e,nx;
}a[100010];
int st[100010],D[100010],t,ans;
void make_al(int s,int e){a[++t].nx=st[s],a[t].e=e,st[s]=t;}
void f(int p,int m){
    int i,cnt=0;
    priority_queue<int> q;
    for(i=st[p];i;i=a[i].nx)q.push(D[a[i].e]);
    D[p]=1;
    for(;!q.empty()&&cnt<m;++cnt){
        D[p]+=q.top();
        q.pop();
    }
}
int main(){
    int i,n,k,p,l,r,m;
    scanf("%d%d",&n,&k);
    for(i=2;i<=n;++i){
        scanf("%d",&p);
        make_al(p,i);
    }
    l=1,r=n;
    while(l<r){
        m=(l+r)/2;
        for(i=n;i;--i)
            f(i,m);
        if(D[1]<k)l=m+1;
        else r=m-1,ans=m;
    }
    printf("%d",ans);
    return 0;
}

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