Submission #1094455

#TimeUsernameProblemLanguageResultExecution timeMemory
1094455mat_jurVillage (BOI20_village)C++17
0 / 100
0 ms460 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";} #define debug(X) cerr << "["#X"]: " << X << '\n'; #else #define cerr if(0)cout #define debug(X) ; #endif using ll = long long; #define all(v) (v).begin(), (v).end() #define ssize(x) int(x.size()) #define fi first #define se second #define mp make_pair #define eb emplace_back void dfs(int v, int p, vector<int> &match, const vector<vector<int>> &g) { for (int u : g[v]) { if (u == p) continue; dfs(u, v, match, g); } if (match[v] != -1) return; for (int u : g[v]) { if (match[u] == -1) { match[v] = u; match[u] = v; } } } vector<int> matching(const vector<vector<int>> &g) { int n = ssize(g); vector<int> match(n, -1); dfs(0, -1, match, g); return match; } void dfs_cent(int v, int p, vector<int> &s, const vector<vector<int>> &g) { s[v] = 1; for (int u : g[v]) { if (u == p) continue; dfs_cent(u, v, s, g); s[v] += s[u]; } } int centroid(const vector<vector<int>> &g) { int n = ssize(g); vector<int> s(n); dfs_cent(0, -1, s, g); // debug(s); int c = 0; int p = -1; bool is_centroid = false; while (!is_centroid) { is_centroid = true; for (int u : g[c]) { if (u == p) continue; if (s[u] > n/2) { p = c; c = u; is_centroid = false; break; } } } return c; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<vector<int>> g(n); for (int i = 0; i < n-1; ++i) { int u, v; cin >> u >> v; g[u-1].eb(v-1); g[v-1].eb(u-1); } vector<int> match = matching(g); int mn = n; for (int v = 0; v < n; ++v) { if (match[v] != -1) continue; mn++; int u = g[v][0]; match[v] = match[u]; match[u] = v; } int c = centroid(g); vector<int> match_mx(n, -1); vector<vector<int>> sub(ssize(g[c])); ll mx = 0; vector<int> dist(n); function<void(int, int, int)> add_sub = [&](int v, int p, int idx) { mx += dist[v]; sub[idx].eb(v); for (int u : g[v]) { if (u == p) continue; dist[u] = dist[v] + 1; add_sub(u, v, idx); } }; for (int i = 0; i < ssize(g[c]); ++i) { dist[g[c][i]] = 1; add_sub(g[c][i], c, i); } debug(c); debug(sub); sort(all(sub), [&](const vector<int> &a, const vector<int> &b) { return ssize(a) > ssize(b); }); if (n%2 == 0) { int u = sub[0].back(); sub[0].pop_back(); int i = 0; while (i+1 < ssize(sub) && ssize(sub[i]) < ssize(sub[i+1])) { swap(sub[i], sub[i+1]); ++i; } match_mx[c] = u; match_mx[u] = c; } debug(sub); int i = 0; for (int x = 0; x < (n-1)/2; ++x) { debug(i); debug(sub); int u = sub[i].back(); sub[i].pop_back(); int nxt = (i+1)%ssize(sub); while (ssize(sub[nxt]) == 0) { sub.pop_back(); nxt = (i+1)%ssize(sub); } int v = sub[nxt].back(); match_mx[u] = v; match_mx[v] = u; sub[nxt].pop_back(); i = (i+2)%ssize(sub); while (ssize(sub) && ssize(sub.back()) == 0) sub.pop_back(); } if (n%2 == 1) { int u = g[c][0]; match_mx[c] = match_mx[u]; match_mx[u] = c; } debug(match_mx); cout << mn << ' ' << 2*mx << '\n'; for (int x : match) cout << x+1 << ' '; cout << '\n'; for (int x : match_mx) cout << x+1 << ' '; cout << '\n'; // cout << "OK"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...