oj.uz

답안 #14241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
14241 2015-05-07T13:35:57 Z dohyun0324 Company Planning (TOKI14_company) C++
0 / 100
 0 ms 5116 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>con[100010];
int 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;
    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]];
    }
    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();
    return 0;
}

Subtask #1
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 5116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 5116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 5116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 5116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 5116 KB Output isn't correct
2 Halted 0 ms 0 KB -