Submission #897706

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

catinatree

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

const int maxn = 2e5;
vector<int> g[maxn];
int h[maxn];
set<pair<int, int>> ans[maxn];

void dfs(int v, int p, int d) {
    for (const int& u : g[v]) {
        if (u != p) {
            h[u] = h[v] + 1;
            dfs(u, v, d);
            if (!ans[v].empty() && !ans[u].empty() && ans[v].begin()->first + ans[u].begin()->first - 2 * h[v] < d) {
                // at least 1 to delete
                pair<int, int> mV = *ans[v].begin(), mU = *ans[u].begin();
                ans[v].erase(ans[v].begin());
                ans[u].erase(ans[u].begin());
                tuple<int, int, int> oneH = {-1, -1, -1};
                if (ans[v].empty() || ans[v].begin()->first + mU.first - 2 * h[v] >= d) {
                    oneH = max(oneH, make_tuple(mU.first, (!ans[v].empty() ? ans[v].begin()->first : -1), u));
                }
                if (ans[u].empty() || ans[u].begin()->first + mV.first - 2 * h[v] >= d) {
                    oneH = max(oneH, make_tuple(mV.first, (!ans[u].empty() ? ans[u].begin()->first : -1), v));
                }
                if (get<0>(oneH) != -1) {
                    if (get<2>(oneH) == v) {
                        ans[v].emplace(mV);
                    } else {
                        ans[u].emplace(mU);
                    }
                }
            }
            if ((int)ans[v].size() < (int)ans[u].size()) {
                ans[v].swap(ans[u]);
            }
            while (!ans[u].empty()) {
                ans[v].emplace(*ans[u].begin());
                ans[u].erase(ans[u].begin());
            }
        }
    }
    if (ans[v].empty() || ans[v].begin()->first >= h[v] + d) {
        ans[v].emplace(h[v], v);
    }
}

void solve() {
    int n, d;
    cin >> n >> d;
    for (int i = 1; i < n; ++i) {
        int p;
        cin >> p;
        g[p].emplace_back(i);
        g[i].emplace_back(p);
    }
    dfs(0, -1, d);
    cout << ans[0].size() << '\n';
    /*for (const pair<int, int>& v : ans[0]) {
        cout << v.second + 1 << ' ';
    }
    cout << '\n';*/
}

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

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

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