Submission #108712

#	Time	Username	Problem	Language	Result	Execution time	Memory
108712		ckodser	Network (BOI15_net)	C++14	100 / 100	722 ms	53240 KiB

net

#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
const int N = 500005;
int n, ts, st[N];;
vector < int > Adj[N];
void DFS(int v, int p)
{
	st[v] = ts ++;
	for (int &u : Adj[v])
		if (u != p)
			DFS(u, v);
}
bool CMP(int i, int j)
{
	return (st[i] < st[j]);
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i < n; i++)
	{
		int v, u;
		scanf("%d%d", &v, &u);
		Adj[v].push_back(u);
		Adj[u].push_back(v);
	}
	int id = 1;
	for (int i = 1; i <= n; i++)
		if (Adj[i].size() > 1)
			id = i;
	DFS(id, 0);
	vector < int > vec;
	for (int i = 1; i <= n; i++)
		if ((int)Adj[i].size() == 1)
			vec.push_back(i);
	sort(vec.begin(), vec.end(), CMP);
	int len = (int)vec.size() >> 1;
	printf("%d\n", (int)vec.size() - len);
	for (int i = 0; i < (int)vec.size() - len; i++)
		printf("%d %d\n", vec[i], vec[i + len]);
	return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:22: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", &v, &u);
   ~~~~~^~~~~~~~~~~~~~~~

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