Submission #844929

#	Time	Username	Problem	Language	Result	Execution time	Memory
844929		Nhoksocqt1	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	215 ms	50260 KiB

catinatree

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

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 200005;

ii node[MAXN];
vector<int> adj[MAXN];
int dist[MAXN][20], centroidPar[MAXN], centroidDepth[MAXN];
int sz[MAXN], distc[MAXN], depth[MAXN], pa[MAXN], numNode, minDist;
bool dx[MAXN];

void preDfs(int u) {
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it]);
        if(v != pa[u]) {
            depth[v] = 1 + depth[u];
            preDfs(v);
        }
    }
}

int dfsSize(int u, int p) {
    sz[u] = 1;
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it]);
        if(!dx[v] && v != p)
            sz[u] += dfsSize(v, u);
    }

    return sz[u];
}

int centroid(int u, int p, int nSize) {
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it]);
        if(!dx[v] && v != p && sz[v] > nSize / 2)
            return centroid(v, u, nSize);
    }

    return u;
}

void dfsDist(int u, int p, int depth) {
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it]);
        if(!dx[v] && v != p) {
            dist[v][depth] = dist[u][depth] + 1;
            dfsDist(v, u, depth);
        }
    }
}

void build(int u, int p, int depth = 0) {
    int nSize = dfsSize(u, p);
    int c = centroid(u, p, nSize);

    centroidPar[c] = p;
    centroidDepth[c] = depth;
    dfsDist(c, -1, depth);

    dx[c] = 1;
    for (int it = 0; it < sz(adj[c]); ++it) {
        int v(adj[c][it]);
        if(dx[v])
            continue;

        build(v, c, depth + 1);
    }
}

set<int> Set[MAXN];

void update(int u) {
    for (int v = u, cnt = centroidDepth[u]; v != 0; --cnt, v = centroidPar[v])
        distc[v] = min(distc[v], dist[u][cnt]);
}

int query(int u) {
    int res(1e9);
    for (int v = u, cnt = centroidDepth[u]; v != 0; --cnt, v = centroidPar[v])
        res = min(res, distc[v] + dist[u][cnt]);

    return res;
}

void process() {
    cin >> numNode >> minDist;
    for (int u = 2; u <= numNode; ++u) {
        cin >> pa[u]; ++pa[u];
        adj[pa[u]].push_back(u);
        adj[u].push_back(pa[u]);
    }

    depth[1] = 1;
    preDfs(1);

    build(1, 0);
    for (int i = 1; i <= numNode; ++i) {
        node[i] = {depth[i], i};
        distc[i] = 1e9;
    }

    int res(0);
    sort(node + 1, node + numNode + 1, greater<ii>());
    for (int i = 1; i <= numNode; ++i) {
        int u(node[i].se);
        if(query(u) < minDist)
            continue;

        update(u);
        ++res;
    }

    cout << res;
}

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

    process();
    return 0;
}

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