Submission #931717

#TimeUsernameProblemLanguageResultExecution timeMemory
931717vjudge1Network (BOI15_net)C++17
0 / 100
1 ms500 KiB
#include <bits/stdc++.h> #define F first #define S second #define pb push_back using namespace std; const int N = 2000 + 10, LG = 20; int n, h[N], par[N][LG]; bool mark[N]; vector<int> G[N], vec; vector<pair<int, pair<int, int>>> vec1; void dfs(int v = 1, int p = 0) { par[v][0] = p; if (G[v].size() == 1) vec.pb(v); for (auto e : G[v]) if (e ^ p) { h[e] = h[v] + 1; dfs(e, v); } } int lca(int u, int v) { int res = h[u] + h[v]; if (u == v) return 0; if (h[u] < h[v]) swap(u, v); int k = h[u] - h[v]; for (int lg = 0; lg < LG; lg++) if (k & (1 << lg)) u = par[u][lg]; for (int lg = LG - 1; lg >= 0; lg--) if (par[u][lg] ^ par[v][lg]) u = par[u][lg], v = par[v][lg]; return res - 2 * h[par[u][0]]; } int main() { ios:: sync_with_stdio(0), cin.tie(0); cin >> n; for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; G[u].pb(v); G[v].pb(u); } dfs(); for (int i = 0; i < (int)vec.size(); i++) for (int j = i + 1; j < (int)vec.size(); j++) vec1.pb({lca(vec[i], vec[j]), {vec[i], vec[j]}}); sort(vec1.rbegin(), vec1.rend()); cout << ((int)vec.size() + 1) / 2 << endl; for (auto e : vec1) { int cnt = 0; for (int i = 1; i <= n; i++) if (mark[i]) cnt++; if (cnt == (int) vec.size()) return 0; if (!mark[e.S.F] && !mark[e.S.S]) { cout << e.S.F << ' ' << e.S.S << endl; mark[e.S.F] = mark[e.S.S] = true; } else if ((int)vec.size() & 1) if (cnt + 1 == (int)vec.size()) { if (!mark[e.S.S]) return cout << vec1[0].S.F << ' ' << e.S.S << endl, 0; if (!mark[e.S.F]) return cout << vec1[0].S.F << ' ' << e.S.F << endl, 0; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...