oj.uz

Submission #710779

# Submission time Handle Problem Language Result Execution time Memory
710779 2023-03-15T19:06:00 Z stevancv Cat in a tree (BOI17_catinatree) C++14
11 / 100
 4 ms 5076 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 5;
const int inf = 1e9;
vector<int> g[N];
int dep[N], mx[N], ans[N], k;
int Dfs(int s, int d) {
    if (g[s].size() == 0 && d >= k) {
        ans[s] = 1;
        return 0;
    }
    else if (g[s].size() == 0) return inf;
    for (int u : g[s]) {
        int nesto = Dfs(u, d + 1);
        smin(d, nesto + 1);
    }
    if (d >= k) {
        ans[s] = 1;
        return 0;
    }
    return d;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int p; cin >> p;
        g[p].push_back(i);
        dep[i] = dep[p] + 1;
    }
    for (int i = n - 1; i >= 0; i--) {
        mx[i] = dep[i];
        sort(g[i].begin(), g[i].end(), [&] (int xx, int yy) {
            return mx[xx] > mx[yy];
        });
        for (int j : g[i]) smax(mx[i], mx[j]);
    }
    Dfs(0, inf);
    int sum = 0;
    for (int i = 0; i < n; i++) sum += ans[i];
    cout << sum << en;
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 5020 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 4 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4928 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 5024 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 5024 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5032 KB Output is correct
20 Correct 3 ms 5020 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 5020 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 4 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4928 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 5024 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 5024 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5032 KB Output is correct
20 Correct 3 ms 5020 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 3 ms 5012 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Incorrect 4 ms 5076 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 5020 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 4 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4928 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 5024 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 5024 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5032 KB Output is correct
20 Correct 3 ms 5020 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 3 ms 5012 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Incorrect 4 ms 5076 KB Output isn't correct
27 Halted 0 ms 0 KB -