제출 #1361825

#제출 시각아이디문제언어결과실행 시간메모리
1361825iamhereforfunCat in a tree (BOI17_catinatree)C++20
100 / 100
42 ms29804 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))
#define int long long

const int N = 2e5 + 5;
const int M = 1 << 15;
const int B = 18;
const long long K = 2;
const int LG = 20;
const int INF = 1e9 + 5;
const int P = 31;
const int MOD = 1e9 + 7;
const int nx[] = {0, 1, 0, -1}, ny[] = {-1, 0, 1, 0};

int n, d, dp[N], dis[N];
vector<int> adj[N];

void dfs(int c, int p)
{
    vector<pair<int, int>> v;
    for (int i : adj[c])
    {
        if (i == p)
            continue;
        dfs(i, c);
        v.push_back({dis[i] + 1, -dp[i]});
    }
    sort(v.rbegin(), v.rend());
    while (v.size() >= 2)
    {
        // cout << "BRUH\n";
        if (v[v.size() - 1].first + v[v.size() - 2].first >= d)
            break;
        dp[c] += -v.back().second - 1;
        v.pop_back();
    }
    if (v.empty())
    {
        dp[c] = 1;
        dis[c] = 0;
    }
    else
    {
        dis[c] = v.back().first;
        while(!v.empty())
        {
            dp[c] += -v.back().second;
            // cout << v.back().first << " " << v.back().second << "v\n";
            v.pop_back();
        }
    }
    if(dis[c] == d)
    {
        dis[c] = 0;
        dp[c]++;
    }
    // cout << dis[c] << " " <<  dp[c] << " " << c << "\n";
}

inline void solve()
{
    cin >> n >> d;
    for (int x = 1; x < n; x++)
    {
        int i;
        cin >> i;
        adj[x].push_back(i);
        adj[i].push_back(x);
    }
    dfs(0, 0);
    cout << dp[0];
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…