Submission #1121359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121359		ezdp	Cat in a tree (BOI17_catinatree)	C++14	0 / 100	1 ms	340 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];
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;
	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(!pq.empty()){
		auto [_, u] = pq.top(); pq.pop();
		if(block[u]) continue;
		++ ans;
		dfs_block(u, d);
	}
	cout << ans << endl;
}

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:41:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |   auto [_, u] = pq.top(); pq.pop();
      |        ^

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