Submission #985657

#	Time	Username	Problem	Language	Result	Execution time	Memory
985657		OAleksa	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	104 ms	20176 KiB

catinatree

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 2e5 + 69;
int n, d;
int dep[N], vis[N], dis[N];
vector<int> g[N];
void dfs(int v, int p) {
	dep[v] = dep[p] + 1;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
	}
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> d;
  	for (int i = 2;i <= n;i++) {
  		int x;
  		cin >> x;
  		++x;
  		g[x].push_back(i);
  		g[i].push_back(x);
  	}
  	dfs(1, 0);
  	for (int i = 1;i <= n;i++)
  		dis[i] = 1e9;
  	int ans = 0;
  	vector<pair<int, int>> dd;
  	for (int i = 1;i <= n;i++) 
  		dd.push_back({dep[i], i});
  	sort(dd.rbegin(), dd.rend());
  	for (int j = 0;j < n;j++) {
  		int i = dd[j].s;
  		if (dis[i] >= d) {
  			ans += 1;
  			queue<int> q;
  			q.push(i);
  			dis[i] = 0;
  			while (!q.empty()) {
  				auto v = q.front();
  				q.pop();
  				for (auto u : g[v]) {
  					if (dis[u] <= dis[v] + 1)
  						continue;
  					dis[u] = dis[v] + 1;
  					if (dis[u] < d)
  						q.push(u);
  				}
  			}
  		}
  	}
  	cout << ans << '\n';
  }
  return 0; 
}

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