Submission #1035890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035890		phoenix	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	345 ms	109244 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;

const int N = 200200;

int n, D;
int p[N];
int d[N];
vector<int> g[N];

int sz[N];
bool rv[N];

int calc(int s, int p) {
    sz[s] = 1;
    for (int to : g[s]) if (to != p && !rv[to]) {
        sz[s] += calc(to, s);
    }
    return sz[s];
}

int find_centroid(int s, int p, int m) {
    for (int to : g[s]) if (to != p && !rv[to]) {
        if (sz[to] * 2 > m) 
            return find_centroid(to, s, m);
    }
    return s;
}

vector<pair<int, int>> par[N];
vector<pair<int, int>> cmp[N];

int iter;
int dst[N];
int vis[N];
queue<int> q;

void bfs(int c) {
    ++iter;
    dst[c] = 0;
    vis[c] = iter;
    q.push(c);
    while (!q.empty()) {
        int s = q.front();
        cmp[c].push_back({s, dst[s]});
        par[s].push_back({c, dst[s]});
        q.pop();
        for (int to : g[s]) if (vis[to] != iter && !rv[to]) {
            vis[to] = iter;
            dst[to] = dst[s] + 1;
            q.push(to);
        }
    }
    reverse(cmp[c].begin(), cmp[c].end());
}

void decompose(int s, int p = 0) {
    int C = find_centroid(s, s, calc(s, s));
    bfs(C);
    rv[C] = true;
    for (int to : g[C]) if (!rv[to]) {
        decompose(to, C);
    }
}

bool us[N];

void del(int v) {
    for (auto [c, dist] : par[v]) {
        while (!cmp[c].empty() && cmp[c].back().second + dist <= D) {
            us[cmp[c].back().first] = true;
            cmp[c].pop_back();
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> D;
    D--;
    for (int i = 1; i < n; i++) {
        cin >> p[i];
        g[p[i]].push_back(i);
        g[i].push_back(p[i]);
    }
    for (int i = 1; i < n; i++) 
        d[i] = d[p[i]] + 1;
    
    decompose(1);
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        return d[a] > d[b];
    });
    int res = 0;
    for (int c : ord) if (!us[c]) {
        res++;
        del(c);
    }
    cout << res;
}

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