Submission #924919

#	Time	Username	Problem	Language	Result	Execution time	Memory
924919		Ghulam_Junaid	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	1057 ms	15984 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 10;
int n, d, par[N], dist[N], vis[N];
bool mark[N];

vector<int> g[N];
 
void dfs(int v, int p = -1){
    for (int u : g[v]){
        if (u == p) continue;
        dist[u] = dist[v] + 1;
        dfs(u, v);
    }
}
 
void dfs_vis(int v, int start, int cur = 0, int p = -1){
    if (cur + 1 == d) return;
    
    for (int u : g[v]){
        if (u == p) continue;
        int my = (d - vis[u] + 1) * (bool(vis[u]));
        if (my > (d - vis[v])) continue;
        vis[u] = vis[v] + 1;
        dfs_vis(u, start, cur + 1, v);
    }
}
 
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];
        g[par[i]].push_back(i);
        g[i].push_back(par[i]);
    }
 
    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());

    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;
 
        ans++;
        vis[v] = 1;
        dfs_vis(v, v);
    }
 
    cout << ans << endl;
}

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