Submission #924925

#	Time	Username	Problem	Language	Result	Execution time	Memory
924925		Ghulam_Junaid	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	787 ms	38088 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 10;
const int LG = 18;
const int T = 70;

int n, d, par[N][LG], dist[N], vis[N], h[N];
bool mark[N];

vector<int> g[N], buffer;
 
void dfs(int v, int p = -1){
    for (int u : g[v]){
        if (u == p) continue;
        dist[u] = dist[v] + 1;
        
        h[u] = h[v] + 1;
        for (int i = 1; i < LG; i ++)
            if (par[u][i] != -1)
                par[u][i] = par[par[u][i - 1]][i - 1];

        dfs(u, v);
    }
}

inline int lca(int u, int v){
    if (h[u] > h[v])
        swap(u, v);

    int d = h[v] - h[u];
    for (int i = 0; i < LG; i ++)
        if ((1 << i) & d)
            v = par[v][i];

    if (u == v) return v;

    for (int i = LG - 1; i >= 0; i --)
        if (par[u][i] != par[v][i])
            u = par[u][i], v = par[v][i];

    return par[v][0];
}

inline int distance(int u, int v){
    return h[u] + h[v] - 2 * h[lca(u, v)];
}
 
inline void bfs(){
    for (int i = 0; i < n; i ++)
        dist[i] = n + 100;

    queue<int> q;
    for (int x : buffer){
        q.push(x);
        dist[x] = 0;
    }

    while (!q.empty()){
        int v = q.front();
        q.pop();

        for (int u : g[v]){
            if (dist[u] > dist[v] + 1){
                dist[u] = dist[v] + 1;
                if (dist[u] < d)
                    q.push(u);
            }
        }
    }

    for (int i = 0; i < n; i ++)
        vis[i] |= (dist[i] < d);
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> d;
    for (int i = 1; i < n; i ++){
        cin >> par[i][0];
        g[par[i][0]].push_back(i);
        g[i].push_back(par[i][0]);
    }
 
    dfs(0);
 
    vector<pair<int, int>> vec;
    for (int i = 0; i < n; i ++)
        vec.push_back({dist[i], i});
    sort(vec.begin(), vec.end());

    for (int i = 0; i < n; i ++)
        dist[i] = d + 1;

    int ans = 0;
    while (!vec.empty()){
        auto p = vec.back();
        vec.pop_back();
 
        int v = p.second;
        // cout << v << " : " << dist[v] << endl;
        if (vis[v])
            continue;
 
        bool bad = 0;
        for (int x : buffer){
            if (distance(x, v) < d){
                bad = 1;
                break;
            }
        }

        if (bad) continue;

        buffer.push_back(v);
        ans++;

        if (buffer.size() > T){
            bfs();
            buffer.clear();
        }
    }
 
    cout << ans << endl;
}

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