Submission #134621

#	Time	Username	Problem	Language	Result	Execution time	Memory
134621		Ace	Network (BOI15_net)	C++14	100 / 100	634 ms	47916 KiB

net

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

const int N = 5e5;

int n;
vector<int> adj[N+5];
vector<int> leaf;

void dfs(int x, int par){
	if(adj[x].size() == 1){
		leaf.push_back(x);
		return;
	}
	for(int i=0;i<adj[x].size();i++){
		if(adj[x][i] == par) continue;
		dfs(adj[x][i],x);
	}
	return;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int cnt = 0;
	for(int i=1;i<=n;i++){
		if(adj[i].size()!=1){
			dfs(i,-1);
			break;
		}
	}
	if(leaf.size()&1){
		leaf.push_back(leaf[0]);
	}
	printf("%d\n",leaf.size()/2);
	for(int i=0;i<leaf.size()/2;i++){
		printf("%d %d\n",leaf[i],leaf[i+leaf.size()/2]);
	}
	return 0;
}

Compilation message (stderr)

net.cpp: In function 'void dfs(int, int)':
net.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:40:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n",leaf.size()/2);
                ~~~~~~~~~~~~~^
net.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<leaf.size()/2;i++){
              ~^~~~~~~~~~~~~~
net.cpp:30:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = 0;
      ^~~
net.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
net.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~

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