Submission #896169

#TimeUsernameProblemLanguageResultExecution timeMemory
896169ShaShiVillage (BOI20_village)C++17
50 / 100
58 ms17856 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; vector<pii> love; pii tof; void DFS2(int v, int p=-1) { vec.pb(v); for (int u:adj[v]) { if (u == p || u == cent) continue; DFS2(u, v); } } void solve() { vec.pb(cent); for (auto u:adj[cent]) { DFS2(u); } // cout << "$" << vec.size() << endl; for (int i=1; i<=n; i++) { // cout << "!" << i << " " << ((i-1+n/2)%n) << " " << vec[(i-1+n/2)%n] << endl; arr3[i] = vec[(i-1+n/2)%n]; } } 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]; for (int i=1; i<=n; i++) arr4[arr3[i]] = i; 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++) 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...