Submission #108707

#	Time	Username	Problem	Language	Result	Execution time	Memory
108707		MAMBA	Network (BOI15_net)	C++17	100 / 100	769 ms	80720 KiB

net

#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for (int i = j; i < k; i++)
#define pb push_back
#define for_all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

inline void fileIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

template<class T , class S>
inline void smin(T &a, S b) {
	if (a > b)
		a = b;
}

template<class T , class S>
inline void smax(T &a, S b) {
	if (a < b)
		a = b;
}

constexpr int N = 1e6 + 10;

int n;
vi adj[N];
vector<pii> res;
pii dp[N];

void dfs(int v, int par = 0) {
	vi st;
	if (adj[v].size() == 1) {
		dp[v] = {v , -1};
		return;
	}
	for (auto e : adj[v])
		if (e ^ par) {
			dfs(e, v);
			if (st.size() > 1) {
				res.pb({st.back() , dp[e].first});
				st.pop_back();
				dp[e].first = -1;
			}
			if (st.size() > 1 && dp[e].second != -1) {
				res.pb({st.back() , dp[e].second});
				st.pop_back();
				dp[e].second = -1;
			}
			if (dp[e].first != -1)
				st.pb(dp[e].first);
			if (dp[e].second != -1)
				st.pb(dp[e].second);
		}
	if (st.size() == 3) {
		res.pb({st[0] , st[1]});
		int me = st.back();
		st.clear();
		st.pb(me);
	}
	dp[v].first = st.back();
	st.pop_back();
	dp[v].second = st.empty() ? -1 : st.back();

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	rep(i , 1 , n) {
		int u , v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	rep(i , 1 , n + 1)
		if (adj[i].size() > 1) {
			dfs(i);
			if (dp[i].first != -1 && dp[i].second != -1) 
				res.pb(dp[i]);
			else
				res.pb({dp[i].first , i});
			break;
		}

	cout << res.size() << endl;
	for (auto e : res)
		cout <<e.first << ' ' << e.second << '\n';


	return 0;
}

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