제출 #476660

#제출 시각아이디문제언어결과실행 시간메모리
476660thiago_bastosNetwork (BOI15_net)C++17
0 / 100
0 ms204 KiB
#include "bits/stdc++.h" using namespace std; using i64 = long long; using u64 = unsigned long long; using i32 = int; using u32 = unsigned; using i16 = short; using u16 = unsigned short; using ld = long double; using ii = pair<int, int>; vector<vector<int>> g; vector<int> leaves; int n; void preprocess(int u, int p = -1) { leaves[u] = 0; if((int)g[u].size() == 1) ++leaves[u]; for(int v : g[u]) { if(v == p) continue; preprocess(v, u); leaves[u] += leaves[v]; } } int dfs(int u, int p = -1) { int max_leaves = 0; if(p != -1) max_leaves = leaves[0] - leaves[u]; for(int v : g[u]) { if(v == p) continue; max_leaves = max(max_leaves, leaves[v]); } if(max_leaves <= leaves[0] / 2) return u; for(int v : g[u]) { if(v == p) continue; int w = dfs(v, u); if(w != -1) return w; } return -1; } void solve() { cin >> n; g.resize(n); leaves.resize(n); for(int i = 1; i < n; ++i) { int u, v; cin >> u >> v; --u, --v; g[u].push_back(v); g[v].push_back(u); } preprocess(0); int v = dfs(0); vector<vector<int>> F; function<void(int, int)> get = [&](int u, int p) { if(g[u].size() == 1) F.back().push_back(u); for(int v : g[u]) { if(v == p) continue; get(v, u); } }; for(int u : g[v]) { F.push_back({}); get(u, v); } vector<ii> pairs; int lo = 0, hi = (int)F.size() - 1; while(lo < hi) { int u = F[lo].back(), v = F[hi].back(); pairs.emplace_back(u + 1, v + 1); F[lo].pop_back(); F[hi].pop_back(); if(F[lo].empty()) ++lo; if(F[hi].empty()) --hi; } for(auto& x : F) { if(x.empty()) continue; int u = x.back(); for(int v = 0; v < n; ++v) { if(v == u || g[v].size() > 1) continue; pairs.emplace_back(u + 1, v + 1); break; } break; } cout << pairs.size() << '\n'; for(auto [u, v] : pairs) cout << u << ' ' << v << '\n'; } int main() { ios_base :: sync_with_stdio(false); cin.tie(0); int t = 1; //cin >> t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...