Submission #876013

#	Time	Username	Problem	Language	Result	Execution time	Memory
876013		vjudge1	Network (BOI15_net)	C++17	100 / 100	651 ms	41908 KiB

net

#include <bits/stdc++.h>
using namespace std;
bool seen[500005]={false};
vector<int> links[500005];
vector<int> roots;
int last=-1;
void dfs(int at){
	if(seen[at]){
		return;
	}
	seen[at]=true;
	if(links[at].size()==1){
		roots.push_back(at);
	}
	for(int to:links[at]){
		if(!seen[to]) dfs(to);
	}
}
int main(){
	int n;
	cin>>n;
	for(int i=0; i<n-1; i++){
		int a,b;
		cin>>a>>b;
		links[a].push_back(b);
		links[b].push_back(a);
	}
	dfs(1);
	int total=roots.size()/2;
	vector<pair<int,int>> ans;
	for(int i=0; i<total; i++){
		ans.push_back({roots[i],roots[i+total]});
	}
	if(roots.size()%2==1){
		ans.push_back({roots[0],roots[roots.size()-1]});
		total++;
	}
	cout<<total<<endl;
	for(int i=0; i<ans.size(); i++){
		cout<<ans[i].first<<' '<<ans[i].second<<endl;
	}
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=0; i<ans.size(); i++){
      |               ~^~~~~~~~~~~

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