oj.uz

답안 #572489

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
572489 2022-06-04T13:31:41 Z MODDI Cat in a tree (BOI17_catinatree) C++14
0 / 100
 3 ms 4948 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -