Submission #932905

#	Time	Username	Problem	Language	Result	Execution time	Memory
932905		Soshi85	Network (BOI15_net)	C++17	100 / 100	319 ms	46284 KiB

net

#include<bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

#define pb              push_back
#define F               first
#define S               second
#define len(x)          (int)x.size()
#define all(x)          x.begin(),x.end()
#define file            freopen("matrix.txt", "r", stdin);freopen("a.out", "w", stdout);
#define kill(x)         {cout << x << '\n'; continue;}
#define int             long long
#define double			long double

const int maxn = 5e5 + 5, LG = 20, MOD = 1e9+7;// 998244353
const ll inf =  1061109567;

//priority_queue< pii , vector<pii> , greater<pii> pq;

int n;
vector<int> g[maxn], l;

void dfs(int v = 1, int par = 0) {
	if(len(g[v]) == 1) l.pb(v);
	for(int u : g[v]) if(u ^ par) dfs(u, v);
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	
	cin >> n;

	for(int i =0; i<n-1; ++i) {
		int v, u;
		cin >> v >> u;
		g[v].pb(u);
		g[u].pb(v);
	}

	dfs();

	cout << (len(l) + 1)/2 << '\n';

	for(int i = 0; i < (len(l)+1)/2; ++i)
		cout << l[i] << ' ' << l[i+len(l)/2] << '\n';

}

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