Submission #218333

#	Time	Username	Problem	Language	Result	Execution time	Memory
218333		socho	Network (BOI15_net)	C++14	100 / 100	1132 ms	48036 KiB

net

#include "bits/stdc++.h"
using namespace std;
// #define int long long

const int MXN = 500005;
vector<int> adj[MXN];

vector<int> lvs;

void dfs_down(int node, int last) {
	bool tr = true;
	for (int i=0; i<adj[node].size(); i++) {
		if (adj[node][i] == last) continue;
		int o = adj[node][i];
		tr = false;
		dfs_down(o, node);
	}
	if (tr) {
		lvs.push_back(node);
	}
}

signed main() {
	
	int n;
	cin >> n;
	for (int i=1; i<n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	bool need = true;
	int root = -1;
	for (int j=1; j<=n && need; j++) {
		if (adj[j].size() < 2) continue;
		dfs_down(j, -1);
		root = j;
		need = false;
	}
	
	int x = (lvs.size() + 1) / 2;
	cout << x << endl; // needed
	
	vector<int> le, ri;
	for (int i=0; i<x; i++) {
		le.push_back(lvs[i]);
	}
	for (int i=x; i<lvs.size(); i++) {
		ri.push_back(lvs[i]);
	}
	if (ri.size() < le.size()) ri.push_back(root);
	
	for (int i=0; i<x; i++) {
		cout << le[i] << ' ' << ri[i] << endl;
	}
	
	
}	

Compilation message (stderr)

net.cpp: In function 'void dfs_down(int, int)':
net.cpp:12:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:50:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=x; i<lvs.size(); i++) {
                ~^~~~~~~~~~~

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