Submission #1121360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121360		ezdp	Cat in a tree (BOI17_catinatree)	C++14	0 / 100	2 ms	336 KiB

catinatree

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

const int MAXN = 2e5;

template<class T> using matrix = vector<vector<T>>;

matrix<int> G;
int n, d, depths[MAXN + 5], block[MAXN + 5], par[MAXN + 5], blocked;
priority_queue<pair<int, int>> pq;

void dfs(int u = 1, int d = 0){
	depths[u] = d;
	for(auto v : G[u]){
		dfs(v, d + 1);
	}
}

void dfs_block(int u, int d){
	if(d == 0 || block[u]) return;
	block[u] = true; ++ blocked;
	if(u != 1) dfs_block(par[u], d - 1);
	for(auto v : G[u]){
		dfs_block(v, d - 1);
	}
}

int main(){
	cin >> n >> d;
	G = matrix<int>(n + 1);
	for(int i = 2; i <= n; i ++){
		cin >> par[i]; ++ par[i];
		G[par[i]].push_back(i);
	}
	dfs();
	for(int u = 1; u <= n; u ++){
		pq.push({depths[u], u});
	}
	int ans = 0;
	while(blocked < n){
		/*
		auto [_, u] = pq.top(); pq.pop();
		if(block[u]) continue;
		++ ans;
		dfs_block(u, d);
		*/
		pair<int, int> best = {0, 0};
		for(int i = 1; i <= n; i ++){
			if(block[i]) continue;
			best = max(best, {depths[i], i});
		}
		++ ans;
		dfs_block(best.second, d);
	}
	cout << ans << endl;
}

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