oj.uz

Submission #14249

# Submission time Handle Problem Language Result Execution time Memory
14249 2015-05-07T15:10:02 Z dohyun0324 Company Planning (TOKI14_company) C++
0 / 100
 1 ms 5508 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>con[100010];
int ch[100010],maxi,arr[100010],t,n,m,par[100010],d[100010],num[100010];
void dfs(int x,int k)
{
    int i;
    for(i=0;i<con[x].size();i++){
        dfs(con[x][i],k);
    }
    t=0; d[x]=0;
    for(i=0;i<con[x].size();i++){
        arr[++t]=d[con[x][i]]-num[con[x][i]];
        d[x]+=num[con[x][i]];
    }
    sort(arr+1,arr+t+1);
    for(i=1;i<=min(k,t);i++) d[x]+=arr[i];
}
int pro(int x){
    dfs(1,x);
    return n-d[1];
}
void bsearch()
{
    int st=1,en=n,mid;
    while(st!=en){
        mid=(st+en)/2;
        if(pro(mid)>=m) en=mid;
        else st=mid+1;
    }
    printf("%d",st);
}
void init(int x)
{
    int i,b;
    for(i=0;i<con[x].size();i++){
        init(con[x][i]);
        num[x]+=num[con[x][i]];
    }
    num[x]++;
}
int main()
{
    int i;
    scanf("%d %d",&n,&m);
    for(i=2;i<=n;i++){
        scanf("%d",&par[i]);
        con[par[i]].push_back(i);
    }
    for(i=1;i<=n;i++)
    {
        ch[par[i]]++;
        if(maxi<ch[par[i]]) maxi=ch[par[i]];
    }
   // init(1);
    //bsearch();
    printf("%d",maxi);
    return 0;
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 5508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 5508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 5508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 5508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 5508 KB Output isn't correct
2 Halted 0 ms 0 KB -