Submission #656057

#	Time	Username	Problem	Language	Result	Execution time	Memory
656057		mosaev	Network (BOI15_net)	C++17	100 / 100	461 ms	49096 KiB

net

#include <bits/stdc++.h>
#include <set>
#include <map>
#include <unordered_map>
using namespace std;
#define ll long long
#define N (ll)(5e5+5)
#define NP (2097155ll)
#define M ((ll)1e9+7)
#define fi first
#define se second
ll n, ct, r;
vector<ll> v[N], k;
vector<pair<ll, ll>> ans;
void dfs(ll s, ll p) {
	for (auto x : v[s]) if (x != p) dfs(x, s);
	if (v[s].size() == 1) k.push_back(s);
}
int main() {
#define int ll
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n; ll a, b; for (int i = 1; i < n; i++) cin >> a >> b, v[a].push_back(b), v[b].push_back(a);
	dfs(1, 0);
	cout << (k.size() / 2 + (k.size() & 1)) << '\n';
	if (k.size() & 1) {
		cout << k.back() << ' ' << k[0] << '\n'; k.pop_back();
	}
	for (int i = 0; i < k.size()/2; i++) cout << k[i] << ' ' << k[i + k.size() / 2] << '\n';
}

Compilation message (stderr)

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

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