Submission #762846

#	Time	Username	Problem	Language	Result	Execution time	Memory
762846		ThegeekKnight16	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	265 ms	58928 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
const int MAXK = 21;
set<pair<int, int> > verts;
array<vector<int>, MAXN> grafo;
array<int, MAXN> Prof;
array<set<pair<int, int> >, MAXN> active;
//            Prof  id
int dp[MAXN][MAXK];
int N, D;
int tmp = 0;

void dfs(int v, int p)
{
    Prof[v] = Prof[p]+1;
    active[v].emplace(Prof[v], v);

    for (auto viz : grafo[v])
    {
        if (viz == p) continue;
        dfs(viz, v);

        set<pair<int, int> > temp;
        if (active[viz].size() > active[v].size()) swap(active[v], active[viz]);
        for (auto [prof, cur] : active[viz])
        {
            if (active[v].empty()) {temp.emplace(prof, cur); continue;}
            auto lastPar = active[v].lower_bound(make_pair(prof, -1));
            if (lastPar == active[v].end())
            {
                if (prof + active[v].rbegin()->first - 2*Prof[v] + 1 <= D) active[v].clear();
                temp.emplace(prof, cur);
                continue;
            }
            int lastProf = lastPar->first;
            if (prof + lastProf - 2*Prof[v] + 1 <= D) continue;
            for (auto it = active[v].begin(); it != lastPar && prof + it->first - 2*Prof[v] + 1 <= D; it = active[v].erase(it));
            temp.emplace(prof, cur);
        }

        for (auto x : temp) active[v].insert(x);
        temp.clear();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> D;
    for (int i = 1; i < N; i++)
    {
        int X;
        cin >> X;
        grafo[X].push_back(i);
        grafo[i].push_back(X);
    }

    // for (int k = 0; k < MAXK; k++) dp[N][k] = N;
    dfs(0, 0);

    cout << active[0].size() << '\n';
}

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