제출 #1360911

#제출 시각아이디문제언어결과실행 시간메모리
1360911eyadoozCat in a tree (BOI17_catinatree)C++20
0 / 100
1 ms344 KiB
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define endl '\n'

vector<int> adj[200005];
map<int, priority_queue<int>> s;
int n, D;
void dfs(int x, int p=-1, int d=0) 
{
    for(auto i : adj[x]) 
    {
        if(i==p) continue;
        dfs(i, x, d+1);
    }
    priority_queue<int> cur;
    int mn=INT_MAX;
    for(auto i : adj[x]) 
    {
        if(i==p) continue;
        while(sz(s[i])&&sz(cur)&&((cur.top()+s[i].top())-(2*d))<D)
        {
            auto f=max(cur.top(), s[i].top());
            cur.pop();
            s[i].pop();
            cur.push(f);
            mn=min(mn, f);
        } 
        while(sz(s[i]))
        {
            cur.push(s[i].top());
            mn=min(mn, s[i].top());
            s[i].pop();
        } 
    }
    if(sz(cur)&&mn-d>=D) cur.push(d);
    else if(cur.empty()) cur.push(d);
    s[x]=cur;
}
int main()
{
    cin.tie(0) -> sync_with_stdio(0);

    cin >> n >> D;
    for(int i = 1;i < n;i++) 
    {
        int x;
        cin >> x;
        adj[i].pb(x);
        adj[x].pb(i);
    }
    dfs(0);
    cout << sz(s[0]) << endl;
}
    
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…