oj.uz

Submission #553490

# Submission time Handle Problem Language Result Execution time Memory
553490 2022-04-26T03:31:56 Z Talha_Taki Cat in a tree (BOI17_catinatree) C++17
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
 
typedef long long ll;
typedef pair <int, int> pii;
 
vector <vector <int>> adj;
vector <pii> dp;

int d;

void dfs(int u) {
    if (adj[u].empty()) {
        dp[u] = make_pair(1, 0);
        return ;
    }

    int ans = 0;
    vector <pii> a;
    for(int v : adj[u]) {
        dfs(v);
        a.push_back(dp[v]);
        ans += dp[v].first;
    }

    sort(a.begin(), a.end(), [] (const pii &a, const pii &b) {
        return a.second < b.second;
    });

    int dist = a[0].second + 1;
    int size = adj[u].size();
    for(int i = 1; i < size; ++i) {
        if (a[i-1].second + 2 + a[i].second < d) {
            ans--;
            dist = a[i].second + 1;
        }
        else {
            if (a[i-1].second + 1 >= d) {
                ans++;
                dist = 0;
            }
            break;
        }
    }

    dp[u] = make_pair(ans, dist);
}

 
int main(const int argc, const char *argv[]) {
 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n >> d;

    adj.resize(n);
    dp.resize(n);

    for(int i = 1; i < n; ++i) {
        int p;
        cin >> p;

        adj[p].push_back(i);
    }

    dfs(0);

    cout << dp[0].first;

    return 0;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 49.0

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