Submission #572489

#	Time	Username	Problem	Language	Result	Execution time	Memory
572489		MODDI	Cat in a tree (BOI17_catinatree)	C++14	0 / 100	3 ms	4948 KiB

catinatree

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n, d;
vi G[200050];
int furthest(int start){
	queue<pii> q;
	q.push(mp(start, 0));
	bool vis[n];
	memset(vis, false, sizeof(vis));
	vis[start] = true;
	int sz = 0, id = 0;
	while(!q.empty()){
		pii state = q.front(); q.pop();
		int at = state.first;
		int path = state.second;
		if(path > sz){
			path = sz;
			id = at;
		}
		for(auto next : G[at]){
			if(!vis[next]){
				vis[next] = true;
				q.push(mp(next, path + 1));
			}
		}
	}
	return id;
}
int main(){
	cin>>n>>d;
	for(int i = 1; i < n; i++){
		int x;
		cin>>x;
		G[x].pb(i);
		G[i].pb(x);
	}
	int one = furthest(0);
	int	two = furthest(one);
	queue<pii> q;
	q.push(mp(one, 0));
	bool vis[n];
	memset(vis, false, sizeof(vis));
	vis[one] = true;
	int rez = 1;
	while(!q.empty()){
		pii state = q.front();
		q.pop();
		int at = state.first;
		int path = state.second;
		if(path == d){
			rez++;
			path = 0;
		}
		for(auto next : G[at]){
			if(!vis[next]){
				vis[next] = true;
				q.push(mp(next, path+1));
			}
		}
	}
	cout<<rez<<endl;
}

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:45:6: warning: unused variable 'two' [-Wunused-variable]
   45 |  int two = furthest(one);
      |      ^~~

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