Submission #108711

#	Time	Username	Problem	Language	Result	Execution time	Memory
108711		Mahdi_Jfri	Network (BOI15_net)	C++14	100 / 100	844 ms	41416 KiB

net

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

#define ll long long
#define pb push_back

const int maxn = 5e5 + 20;

vector<int> adj[maxn] , tmp;

void dfs(int v , int p = -1)
{
	if((int)adj[v].size() == 1)
		tmp.pb(v);
	for(auto u : adj[v])
		if(u != p)
			dfs(u , v);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	for(int i = 0; i < n - 1; i++)
	{
		int a , b;
		cin >> a >> b;
		a-- , b--;

		adj[a].pb(b);
		adj[b].pb(a);
	}

	int root = -1;
	for(int i = 0; i < n; i++)
		if((int)adj[i].size() != 1)
		{
			root = i;
			dfs(i);
			break;
		}

	int k = tmp.size();
	cout << (k + 1) / 2 << endl;

	for(int i = 0; i < (k + 1) / 2; i++)
		cout << tmp[i] + 1 << " " << tmp[i + k / 2] + 1 << endl;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:39:6: warning: variable 'root' set but not used [-Wunused-but-set-variable]
  int root = -1;
      ^~~~

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