Submission #1034491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034491		sinatbtfard	Network (BOI15_net)	C++17	0 / 100	6 ms	12124 KiB

net

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int maxn = 5e5 + 1;

int n, timer, st[maxn];
vector <int> adj[maxn];
vector <pair <int, int>> check;

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

int main (){
	ios_base::sync_with_stdio(0);
	cin >> n;
	for (int x, y, i = 1; i < n; i++){
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	dfs(1, -1);
	sort(check.begin(), check.end());
	cout << (check.size() + 1) / 2 << '\n';
	assert(check.size() > 1);
	for (int i = 0; i < check.size() / 2; i++)
		cout << check[i].second << " " << check[i + ((check.size()) / 2)].second << '\n';
	if (check.size() & 1)
		cout << 1 << " " << check[(check.size() + 3) / 2].second;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (int i = 0; i < check.size() / 2; i++)
      |                  ~~^~~~~~~~~~~~~~~~~~

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