oj.uz

Submission #853617

# Submission time Handle Problem Language Result Execution time Memory
853617 2023-09-24T17:56:17 Z NK_ Network (BOI15_net) C++17
0 / 100
 1 ms 348 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 18;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; cin >> N;

	vi deg(N);
	V<vi> adj(N); for(int i = 0; i < N - 1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
		deg[u]++, deg[v]++;
	}

	int R = -1; for(int i = 0; i < N; i++) if (deg[i] > 1) R = i;

	vpi ans;
	function<vi(int, int)> dfs = [&](int u, int p) {
		bool leaf = 1;
		
		V<vi> R;
		for(auto& v : adj[u]) if (v != p) {
			leaf = 0;
			vi r = dfs(v, u); R.pb(r);
		}

		if (leaf) return vi{u};

		sort(begin(R), end(R), [&](const auto& x, const auto& y) {
			return sz(x) < sz(y);
		});

		// cout << u << endl;
		vi A, B;
		for(auto r : R) {
			if (sz(r) > 0) {
				A.pb(r[0]);
				// cout << "A " << r[0] << endl;
			}
			if (sz(r) > 1) {
				B.pb(r[1]);
				// cout << "B " << r[1] << endl;
			}
		}
		// cout << endl;

		int amt = sz(A) + sz(B);

		vi r;
		if (amt % 2) { r.pb(A.back()); A.pop_back(); }
		else {
			r.pb(A.back()); A.pop_back();
			r.pb(A.back()); A.pop_back();
		}

		assert((sz(A) + sz(B)) % 2 == 0);

		if (sz(A) % 2) {
			B.pb(A.back()); A.pop_back();
		}

		for(int i = 0; i < sz(A); i += 2) ans.pb(mp(A[i], A[i+1]));
		for(int i = 0; i < sz(B); i += 2) ans.pb(mp(B[i], B[i+1]));

		return r;
	};

	vi r = dfs(R, -1);

	if (sz(r) == 1) ans.pb(mp(r[0], R));
	else ans.pb(mp(r[0], r[1]));

	cout << sz(ans) << nl;
	
	for(auto e : ans) cout << e.f + 1 << " " << e.s + 1 << nl;

	exit(0-0);
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Invalid number of links.
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Invalid number of links.
5 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Invalid number of links.
5 Halted 0 ms 0 KB -