Submission #125052

#	Time	Username	Problem	Language	Result	Execution time	Memory
125052		wilwxk	Network (BOI15_net)	C++14	100 / 100	649 ms	77324 KiB

net

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

const int MAXN=5e5+5;
vector<int> g[MAXN];
int leave[MAXN][2];
vector<pair<int, int> > respf; 
int n, raiz;

void dfs(int cur, int p) {
	if(g[cur].size()==1) leave[cur][0]=cur;
	if(g[cur].size()==1) return;
	for(auto viz : g[cur]) {
		if(viz==p) continue;
		dfs(viz, cur);
		if(!leave[cur][0]) {
			leave[cur][0]=leave[viz][0];
			leave[cur][1]=leave[viz][1];
			continue;
		}
		if(leave[cur][1]) {
			respf.push_back({leave[cur][1], leave[viz][0]});
			leave[cur][1]=leave[viz][1];
		}
		else {
			swap(leave[cur][0], leave[viz][0]);
			if(leave[viz][1]) respf.push_back({leave[viz][0], leave[viz][1]});
			else leave[cur][1]=leave[viz][0];
		}
	}
	// printf("%d >> %d %d\n", cur, leave[cur][0], leave[cur][1]);
}

int main() {
	scanf("%d", &n);
	for(int i=1; i<=n-1; i++) {
		int a, b; scanf("%d %d", &a, &b);
		g[a].push_back(b); g[b].push_back(a);
	}

	for(int i=1; i<=n; i++) if(g[i].size()!=1) raiz=i;
	dfs(raiz, raiz);
	if(!leave[raiz][1]) leave[raiz][1]=raiz;
	respf.push_back({leave[raiz][0], leave[raiz][1]});

	printf("%d\n", respf.size());
	for(auto cara : respf) printf("%d %d\n", cara.first, cara.second);
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:46:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", respf.size());
                 ~~~~~~~~~~~~^
net.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
net.cpp:37: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