Submission #1115986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115986		vjudge1	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	161 ms	34120 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;

#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()

const int NM = 2e5;

int N, D, dep[NM+5];
int parent[NM+5], sz[NM+5];
vector <int> son[NM+5];
priority_queue <pii, vector <pii>, greater <pii> > pq[NM+5];

void make_set(int v){
    parent[v] = v;
    sz[v] = 1;
    pq[v].push(mp(dep[v], v));
}

int find_set(int v){
    return parent[v] == v ? v : parent[v] = find_set(parent[v]);
}

void union_sets(int u, int v){
    u = find_set(u);
    v = find_set(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    parent[v] = u;
    sz[u] += sz[v];
    while (!pq[v].empty()){
        pq[u].push(pq[v].top());
        pq[v].pop();
    }
}

void dfs(int u, int p){
    dep[u] = (p == -1 ? 0 : dep[p]+1);
    for (int v : son[u]) dfs(v, u);
    make_set(u);
    for (int v : son[u]) union_sets(u, v);

    int x = find_set(u);
    while (isz(pq[x]) > 1){
        pii p1 = pq[x].top(); pq[x].pop();
        pii p2 = pq[x].top(); pq[x].pop();

        if (p1.fi+p2.fi-2*dep[u] < D){
            pq[x].push(p2);
            continue;
        }
        pq[x].push(p1);
        pq[x].push(p2);
        break;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> D;
    for (int i = 1; i < N; i++){
        int p; cin >> p;
        son[p].push_back(i);
    }
    dfs(0, -1);
    cout << isz(pq[find_set(0)]);
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49