oj.uz

Submission #18497

# Submission time Handle Problem Language Result Execution time Memory
18497 2016-02-06T11:59:59 Z eaststar Company Planning (TOKI14_company) C++14
0 / 100
 165 ms 3792 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2772 KB Output is correct
2 Correct 0 ms 2772 KB Output is correct
3 Incorrect 0 ms 2772 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2772 KB Output is correct
2 Correct 0 ms 2772 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 0 ms 2772 KB Output is correct
5 Incorrect 0 ms 2772 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2772 KB Output is correct
2 Incorrect 128 ms 2772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2772 KB Output is correct
2 Incorrect 165 ms 3024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2772 KB Output is correct
2 Correct 71 ms 3024 KB Output is correct
3 Correct 164 ms 3792 KB Output is correct
4 Correct 125 ms 2772 KB Output is correct
5 Incorrect 116 ms 2772 KB Output isn't correct
6 Halted 0 ms 0 KB -