oj.uz

Submission #14246

# Submission time Handle Problem Language Result Execution time Memory
14246 2015-05-07T14:53:04 Z dohyun0324 Company Planning (TOKI14_company) C++
0 / 100
 38 ms 8708 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>con[100010];
int 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++){
        if(par[x]==con[x][i]) continue;
        dfs(con[x][i],k);
    }
    t=0; d[x]=0;
    for(i=0;i<con[x].size();i++){
        if(par[x]==con[x][i]) continue;
        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++){
        if(par[x]==con[x][i]) continue;
        init(con[x][i]);
        num[x]+=num[con[x][i]];
    }
    b=con[x].size();
    maxi=max(maxi,b);
    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);
        con[i].push_back(par[i]);
    }
    init(1);
//    bsearch();
    printf("%d",maxi);
    return 0;
}

Subtask #1
0.0 / 12.0

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

Subtask #2
0.0 / 20.0

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

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5116 KB Output is correct
2 Incorrect 38 ms 8152 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 5116 KB Output is correct
2 Incorrect 12 ms 8692 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 5116 KB Output is correct
2 Incorrect 11 ms 8708 KB Output isn't correct
3 Halted 0 ms 0 KB -