Submission #896162

#TimeUsernameProblemLanguageResultExecution timeMemory
896162ShaShiVillage (BOI20_village)C++17
50 / 100
55 ms17744 KiB
#include <bits/stdc++.h> // #define int long long #define F first #define S second #define all(x) x.begin(), x.end() #define kill(x) cout << x << endl, exit(0); #define pb push_back #define mp make_pair #define pii pair<int, int> using namespace std; typedef long long ll; typedef long double ld; const int MAXN = (int)1e5 + 7; const int MOD = 998244353; const int INF = (int)1e9 + 7; int n, m, t, flag, k, u, v, w, ans, ans2, tmp, tmp2, tmp3, tmp4; int arr[MAXN], arr2[MAXN], par[MAXN], h[MAXN], sz[MAXN], cent; int arr3[MAXN], arr4[MAXN]; vector<int> adj[MAXN]; bool DFS(int v, int p=-1) { bool res = 0; for (int u:adj[v]) { if (u != p) res |= DFS(u, v); } if (res) return 0; if (v != 1) { swap(arr[v], arr[p]); ans++; return 1; } swap(arr[1], arr[adj[1][0]]); ans++; return 0; } void DFSsz(int v, int p=-1) { sz[v] = 1; for (int u:adj[v]) { if (u == p) continue; DFSsz(u, v); sz[v] += sz[u]; } } int centroid(int tot, int v, int p=-1) { for (int u:adj[v]) { if (u != p && 2*sz[u] > tot) { return centroid(tot, u, v); } } return v; } vector<int> vec, vec2; vector<pii> love; pii tof; void DFS2(int v, int p=-1) { vec2.pb(v); for (int u:adj[v]) { if (u == p || u == cent) continue; DFS2(u, v); } } void solve() { vec.pb(cent); tmp4 = 1; for (int u:adj[cent]) { love.pb(mp(sz[u], u)); } sort(all(love), greater<pii>()); for (auto cur:love) { u = cur.S; // vec2.clear(); DFS2(u); tmp4 += vec2.size(); while (vec.size() && vec2.size()) { if (tof.F == -1) tof = mp(vec.back(), vec2.back()); swap(arr3[vec.back()], arr3[vec2.back()]); vec2.pop_back(); vec.pop_back(); } while (vec2.size()) { vec.pb(vec2.back()); vec2.pop_back(); } } } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); tof.F = -1; cin >> n; for (int i=1; i<n; i++) { cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } // Min for (int i=1; i<=n; i++) arr[i] = i; DFS(1); for (int i=1; i<=n; i++) arr2[arr[i]] = i; // Max DFSsz(1); cent = centroid(n, 1); DFSsz(cent); for (int i=1; i<=n; i++) arr3[i] = i; solve(); // cout << "!" << cent << endl; for (int i=1; i<=n; i++) if (i != cent) ans2 += sz[i]; if (tmp4%2) { u = vec.back(); v = tof.F; w = tof.S; swap(arr3[v], arr3[w]); arr3[u] = w; arr3[v] = u; arr3[w] = v; } cout << 2*ans << " " << 2*ans2 << endl; for (int i=1; i<=n; i++) cout << arr2[i] << " "; cout << endl; for (int i=1; i<=n; i++) arr4[arr3[i]] = i; for (int i=1; i<=n; i++) cout << arr4[i] << " "; cout << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...