oj.uz

Submission #636675

# Submission time Handle Problem Language Result Execution time Memory
636675 2022-08-29T22:25:51 Z tvladm2009 Cat in a tree (BOI17_catinatree) C++14
0 / 100
 3 ms 5004 KB 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX_N = 2 * 1e5;
vector<int> g[MAX_N + 1];
int dp[MAX_N + 1], dist[MAX_N + 1];
int n, d;

bool cmp(int x, int y) {
    return dist[x] < dist[y];
}

void dfs(int u, int p = -1) {
    if (g[u].size() == 0 || (g[u].size() == 1 && g[u][0] == p)) {
        dp[u] = 1;
        dist[u] = 0;
        return;
    }
    for (int v : g[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
    for (int v : g[u]) {
        if (v != p) {
            dp[u] += dp[v];
        }
    }
    sort(g[u].begin(), g[u].end(), cmp);
    int aux = g[u][0];
    if (g[u][0] == p) {
        aux = g[u][1];
    }
    for (int v : g[u]) {
        if (v != aux && v != p && dist[aux] + dist[v] + 2 < d) {
            dp[u]--;
            aux = u;
        }
    }
    dist[u] = dist[aux] + 1;
    if (dist[u] >= d) {
        dp[u]++;
        dist[u] = 0;
    }
}

int main() {
    cin >> n >> d;
    for (int i = 1; i <= n - 1; i++) {
        int x;
        cin >> x;
        g[x + 1].push_back(i + 1);
    }
    dfs(1);
    cout << dp[1];
    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5000 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 3 ms 4984 KB Output is correct
6 Incorrect 3 ms 4900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5000 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 3 ms 4984 KB Output is correct
6 Incorrect 3 ms 4900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5000 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 3 ms 4984 KB Output is correct
6 Incorrect 3 ms 4900 KB Output isn't correct
7 Halted 0 ms 0 KB -