oj.uz

답안 #849269

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
849269 2023-09-14T10:55:59 Z Vu_CG_Coder Cat in a tree (BOI17_catinatree) C++14
51 / 100
 35 ms 15312 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
int n , d , res = 0;
vector <int> a[N];
int high[N], oder[N], value[N], par[N];

void dfs(int u){
    for (int v : a[u])
    if (v != par[u]){
        high[v] = high[u] + 1;
        par[v] = u;
        dfs(v);
    }
}

int get_min(int u){
    int val = 1e9 , x = 0;
    while (u != 0){
        val = min(val,value[u] + x);
        u = par[u], x++;
    }
    return val;
}

void update(int u){
    int val = 0; res++;
    while (u != 0){
        value[u] = min(value[u],val);
        u = par[u]; val++;
    }
}

bool cmp(int x ,int y){return high[x] > high[y];}
int main(){
    //freopen("txt.inp","r",stdin);
    //freopen("txt.out","w",stdout);
    cin >> n >> d;
    for (int i = 2; i <= n ; i++){
        int x; cin >> x; x++;
        a[x].push_back(i);
        a[i].push_back(x);
    }

    for (int i = 1 ; i < n ; i++){
        // int x , y;
        // cin >> x >> y;
        // a[x].push_back(y);
        // a[y].push_back(x);
        oder[i] = i;
    }
    oder[n] = n; par[1] = 0;
    dfs(1);
    sort(oder + 1,oder + n + 1,cmp);
    memset(value,0x3f,sizeof(value));
    for (int i = 1 ; i <= n ; i++)
        if (get_min(oder[i]) >= d) update(oder[i]);

    cout << res;
    return 0;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Correct 1 ms 4180 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 1 ms 4188 KB Output is correct
8 Correct 1 ms 3932 KB Output is correct
9 Correct 1 ms 4176 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct
11 Correct 1 ms 3932 KB Output is correct
12 Correct 1 ms 3932 KB Output is correct
13 Correct 2 ms 3928 KB Output is correct
14 Correct 1 ms 3932 KB Output is correct
15 Correct 2 ms 3932 KB Output is correct
16 Correct 1 ms 4188 KB Output is correct
17 Correct 1 ms 3928 KB Output is correct
18 Correct 1 ms 3928 KB Output is correct
19 Correct 1 ms 3932 KB Output is correct
20 Correct 1 ms 4188 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Correct 1 ms 4180 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 1 ms 4188 KB Output is correct
8 Correct 1 ms 3932 KB Output is correct
9 Correct 1 ms 4176 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct
11 Correct 1 ms 3932 KB Output is correct
12 Correct 1 ms 3932 KB Output is correct
13 Correct 2 ms 3928 KB Output is correct
14 Correct 1 ms 3932 KB Output is correct
15 Correct 2 ms 3932 KB Output is correct
16 Correct 1 ms 4188 KB Output is correct
17 Correct 1 ms 3928 KB Output is correct
18 Correct 1 ms 3928 KB Output is correct
19 Correct 1 ms 3932 KB Output is correct
20 Correct 1 ms 4188 KB Output is correct
21 Correct 4 ms 4188 KB Output is correct
22 Correct 1 ms 4188 KB Output is correct
23 Correct 1 ms 4188 KB Output is correct
24 Correct 2 ms 4344 KB Output is correct
25 Correct 2 ms 4184 KB Output is correct
26 Correct 2 ms 4188 KB Output is correct
27 Correct 2 ms 4188 KB Output is correct
28 Correct 2 ms 4188 KB Output is correct
29 Correct 2 ms 4188 KB Output is correct
30 Correct 2 ms 4188 KB Output is correct
31 Correct 2 ms 4188 KB Output is correct
32 Correct 2 ms 4188 KB Output is correct
33 Correct 2 ms 4184 KB Output is correct
34 Correct 2 ms 4188 KB Output is correct
35 Correct 2 ms 4192 KB Output is correct
36 Correct 2 ms 4188 KB Output is correct
37 Correct 2 ms 4188 KB Output is correct
38 Correct 2 ms 4188 KB Output is correct
39 Correct 3 ms 4060 KB Output is correct
40 Correct 4 ms 4188 KB Output is correct

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Correct 1 ms 4180 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 1 ms 4188 KB Output is correct
8 Correct 1 ms 3932 KB Output is correct
9 Correct 1 ms 4176 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct
11 Correct 1 ms 3932 KB Output is correct
12 Correct 1 ms 3932 KB Output is correct
13 Correct 2 ms 3928 KB Output is correct
14 Correct 1 ms 3932 KB Output is correct
15 Correct 2 ms 3932 KB Output is correct
16 Correct 1 ms 4188 KB Output is correct
17 Correct 1 ms 3928 KB Output is correct
18 Correct 1 ms 3928 KB Output is correct
19 Correct 1 ms 3932 KB Output is correct
20 Correct 1 ms 4188 KB Output is correct
21 Correct 4 ms 4188 KB Output is correct
22 Correct 1 ms 4188 KB Output is correct
23 Correct 1 ms 4188 KB Output is correct
24 Correct 2 ms 4344 KB Output is correct
25 Correct 2 ms 4184 KB Output is correct
26 Correct 2 ms 4188 KB Output is correct
27 Correct 2 ms 4188 KB Output is correct
28 Correct 2 ms 4188 KB Output is correct
29 Correct 2 ms 4188 KB Output is correct
30 Correct 2 ms 4188 KB Output is correct
31 Correct 2 ms 4188 KB Output is correct
32 Correct 2 ms 4188 KB Output is correct
33 Correct 2 ms 4184 KB Output is correct
34 Correct 2 ms 4188 KB Output is correct
35 Correct 2 ms 4192 KB Output is correct
36 Correct 2 ms 4188 KB Output is correct
37 Correct 2 ms 4188 KB Output is correct
38 Correct 2 ms 4188 KB Output is correct
39 Correct 3 ms 4060 KB Output is correct
40 Correct 4 ms 4188 KB Output is correct
41 Runtime error 35 ms 15312 KB Execution killed with signal 11
42 Halted 0 ms 0 KB -