Submission #553467

#	Time	Username	Problem	Language	Result	Execution time	Memory
553467		Talha_Taki	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	1091 ms	45376 KiB

catinatree

#include <bits/stdc++.h>
 
using namespace std;
 
 
typedef long long ll;
typedef pair <int, int> pii;
 
vector <vector <int>> adj, parent;
vector <int> tin, tout, depth;
set <pii, greater <pii>> S;

int k, timer;

void dfs(int u, int p, int d) {
    depth[u] = d;
    tin[u] = ++timer;

    S.insert({d, u});
    for(int i = 1; i <= k; ++i) parent[u][i] = parent[parent[u][i-1]][i-1];
    for(int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u, d+1);
    }

    tout[u] = ++timer;
}

inline bool isAncestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
    if (isAncestor(u, v)) return u;
    if (isAncestor(v, u)) return v;

    for(int i = k; i >= 0; --i) {
        if (!isAncestor(parent[u][i], v)) {
            u = parent[u][i];
        }
    }

    return parent[u][0];
}

int dist(int a, int b) {
    return depth[a] + depth[b] - (depth[lca(a, b)]<<1);
}
 
int main(const int argc, const char *argv[]) {
 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, d;
    cin >> n >> d;

    k = ceil(log2(n));
    adj.resize(n+1);
    parent.assign(n+1, vector <int> (k+1, 0));
    tin.resize(n+1);
    tout.resize(n+1);
    depth.resize(n+1);

    tin[0] = 0;
    tout[0] = n<<2|1;

    for(int i = 2; i <= n; ++i) {
        int p;
        cin >> p;
        ++p;

        parent[i][0] = p;
        adj[i].push_back(parent[i][0]);
        adj[parent[i][0]].push_back(i);
    }
    dfs(1, 0, 0);

    int ans = 0;
    while (!S.empty()) {
        auto u = (*S.begin()).second;
        ans++;

        for(int i = 1; i <= n; ++i) {
            if (dist(u, i) < d) {
                S.erase({depth[i], i});
            }
        }
    }


    cout << ans;

 
    return 0;
}

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