Submission #907726

#	Time	Username	Problem	Language	Result	Execution time	Memory
907726		shoryu386	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	1008 ms	22088 KiB

catinatree

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

#define int long long

vector<int> adj[200007];

int depth[200007];
bitset<200007> marked;
void dfs(int x, int p, int d){
	depth[x] = d;
	
	for (auto y : adj[x]){
		if (y == p) continue;
		dfs(y, x, d+1);
	}
}

int dfsMarked(int x, int p){
	int ans = INT_MAX;
	if (marked[x]) return 0;
	
	for (auto y : adj[x]){
		if (y == p) continue;
		ans = min(dfsMarked(y, x) + 1, ans);
	}
	return ans;
}

main(){
	int n, d; cin >> n >> d;
	int p[n];
	for (int x = 1; x < n; x++){
		cin >> p[x];
		
		adj[x].push_back(p[x]);
		adj[p[x]].push_back(x);
	}
	
	dfs(0, -1, 0);
	
	vector<int> depthOrder[200007];
	for (int x = 0; x < n; x++){
		depthOrder[depth[x]].push_back(x);
	}
	
	int ans = 0;
	for (int x = 200000; x > -1; x--){
		for (auto y : depthOrder[x]){
			//cout << y << ' ' << dfsMarked(y, -1) << '\n';
			
			if (dfsMarked(y, -1) >= d){
				marked[y] = 1;
				ans++;
			}
			
			//cout << y << ' ' << marked[y] << '\n';
		}
	}
	cout << ans;
}

Compilation message (stderr)

catinatree.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main(){
      | ^~~~

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