Submission #197949

#	Time	Username	Problem	Language	Result	Execution time	Memory
197949		dndhk	Network (BOI15_net)	C++14	100 / 100	747 ms	51824 KiB

net

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int MAX_N = 500000;

int N;
vector<int> gp[MAX_N+1];
int r;
vector<int> v;
int p[MAX_N+1], sz[MAX_N+1];

void dfs(int x){
	sz[x] = 1;
	for(int i : gp[x]){
		if(i==p[x])	continue;
		p[i] = x;
		dfs(i);
		sz[x]+=sz[i];
	}
}

void dfs2(int x){
	if(sz[x]==1){
		v.pb(x);
	}
	for(int i : gp[x]){
		if(i==p[x])	continue;
		dfs2(i);
	}
}

int main(){
	scanf("%d", &N);
	for(int i=1; i<N; i++){
		int a, b; scanf("%d%d", &a, &b);
		gp[a].pb(b);
		gp[b].pb(a);
	}
	for(int i=1; i<=N; i++){
		if(gp[i].size()>=2){
			r = i;
			break;
		}
	}
	dfs(r);
	dfs2(r);
	printf("%d\n", (v.size()+1)/2);
	int l = v.size()/2;
	for(int i=0; i<=(v.size()-1)/2; i++){
		printf("%d %d\n", v[i], v[i+l]);
	}
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:50:31: 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", (v.size()+1)/2);
                 ~~~~~~~~~~~~~~^
net.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<=(v.size()-1)/2; i++){
               ~^~~~~~~~~~~~~~~~
net.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
net.cpp:38:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~

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