Submission #397643

#	Time	Username	Problem	Language	Result	Execution time	Memory
397643		Iwanttobreakfree	Network (BOI15_net)	C++98	100 / 100	841 ms	58328 KiB

net

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int g,maxi=0;
void dfs(int a,vector<vector<int> >& v,vector<int>& depth,vector<bool>& visto){
	if(depth[a]>maxi){
		maxi=depth[a];
		g=a;
	}
	visto[a]=true;
	for(int x:v[a]){
		if(!visto[x]){
			depth[x]=depth[a]+1;
			dfs(x,v,depth,visto);
		}
	}
}
void bfs(int a,vector<vector<int> >& v){
	int n=v.size();
	int cont=0;
	vector<bool> visto(n,false);
	vector<int> sol;
	queue<int> q;
	q.push(a);
	visto[a]=true;
	while(!q.empty()){
		int nodo=q.front();
		q.pop();
		for(int x:v[nodo]){
			if(!visto[x]){
				visto[x]=true;
				q.push(x);
			}
		}
		if(v[nodo].size()==1)sol.push_back(nodo+1);
	}
	int k=sol.size();
	if(k%2){
		cout<<k/2+1<<'\n';
		for(int i=0;i<k/2;i++){
			cout<<sol[i]<<' '<<sol[k/2+i]<<'\n';
		}
		cout<<sol[k-1]<<' '<<sol[0]<<'\n';
	}
	else{
		cout<<k/2<<'\n';
		for(int i=0;i<k/2;i++){
			cout<<sol[i]<<' '<<sol[k/2+i]<<'\n';
		}
	}
}
int main(){
	int n,a,b;
	cin>>n;
	vector<vector<int> >v(n,vector<int>());
	for(int i=0;i<n-1;i++){
		cin>>a>>b;
		a--;b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	vector<bool> visto(n,false);
	vector<int> depth(n,0);
	dfs(0,v,depth,visto);
	bfs(g,v);
}

Compilation message (stderr)

net.cpp: In function 'void bfs(int, std::vector<std::vector<int> >&)':
net.cpp:21:6: warning: unused variable 'cont' [-Wunused-variable]
   21 |  int cont=0;
      |      ^~~~

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37