제출 #1160078

#제출 시각아이디문제언어결과실행 시간메모리
1160078countlessVillage (BOI20_village)C++20
25 / 100
1094 ms18500 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<long long> vll; typedef vector<vector<long long>> vvll; typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef set<int> si; typedef set<long long> sll; const ll MOD = 998244353; const ld EPS = 1e-12; #define endl "\n" #define sp <<" "<< #define forn(i, n) for(ll i = 0; i < n; i++) #define rforn(i, n) for(ll i = n; i >= 0; i--) #define dbg(x) cout << #x << " = " << x << endl #define mp make_pair #define pb push_back #define fi first #define se second #define INF 1e18 #define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((ll)(x).size()) int N, LOGN; int mn = 0, mx = 0, timer = 0; vector<int> ansMin, ansMax, depth, tin, tout, par; vector<vector<int>> up; // mem this void binLift(vector<vector<int>> &adj) { for (int i = 0; i < N; i++) { up[i][0] = par[i]; } for (int j = 1; j < LOGN; j++) { for (int i = 0; i < N; i++) { if (up[i][j - 1] == -1) continue; up[i][j] = up[up[i][j - 1]][j - 1]; } } } // mem this int findLCA(int u, int v) { if (depth[u] < depth[v]) swap(u, v); int diff = depth[u] - depth[v]; for (int i = 0; i < LOGN; i++) { if (diff & (1 << i)) { u = up[u][i]; } } // one is the ancestor of the other if (u == v) { return u; } // find last non-common ancestor for (int i = 0; i < LOGN; i++) { if (up[u][i] != up[v][i]) { u = up[u][i]; v = up[v][i]; } } return up[u][0]; } // mem this int treeCenter(vector<vector<int>> &adj) { vector<int> deg(N, 0); vector<int> leaves; for (int i = 0; i < N; i++) { deg[i] = adj[i].size(); if (deg[i] == 0 || deg[i] == 1) { leaves.push_back(i); deg[i] = 0; } } int count = leaves.size(); while (count < N) { vector<int> newLeaves; for (auto node : leaves) { for (auto neighbor : adj[node]) { deg[neighbor]--; if (deg[neighbor] == 1) { newLeaves.push_back(neighbor); } } deg[node] = 0; } count += newLeaves.size(); leaves = newLeaves; } return leaves[0]; } void findDepth(int node, int parent, int dep, vector<vector<int>> &adj, vector<int> &depth) { depth[node] = dep; for (auto neighbor : adj[node]) { if (neighbor == parent) continue; findDepth(neighbor, node, dep + 1, adj, depth); } } void minCase(int node, vector<vector<int>> &adj, vector<bool> &vis) { int parent = -1; for (auto neighbor : adj[node]) { if (depth[neighbor] < depth[node]) { parent = neighbor; break; } } // we are at an isolated root if (parent == -1) { vis[node] = true; mn += 2; swap(ansMin[node], ansMin[adj[node][0]]); } else { vis[parent] = true; for (auto neighbor : adj[parent]) { if (depth[neighbor] < depth[parent]) { par[parent] = neighbor; continue; } par[neighbor] = parent; if (vis[neighbor]) continue; vis[neighbor] = true; mn += 2; swap(ansMin[parent], ansMin[neighbor]); } } return; } void solution() { cin >> N; LOGN = ceil(log2(N)); ansMin.resize(N), ansMax.resize(N), depth.resize(N), tin.resize(N), tout.resize(N), par.resize(N); up.assign(N, vector<int>(LOGN, -1)); for (int i = 0; i < N; i++) { ansMin[i] = i; ansMax[i] = i; } vector<vector<int>> adj(N); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; u--; v--; adj[u].push_back(v); adj[v].push_back(u); } int center = treeCenter(adj); findDepth(center, -1, 0, adj, depth); // min case vector<bool> vis(N, false); vector<pair<int, int>> depthCopy(N); for (int i = 0; i < N; i++) { depthCopy[i] = {depth[i], i}; } sort(rall(depthCopy)); for (int i = 0; i < N; i++) { if (!vis[depthCopy[i].second]) { minCase(depthCopy[i].second, adj, vis); } } // max case par[center] = -1; binLift(adj); vis.assign(N, false); depthCopy.clear(), depthCopy.resize(N); for (int i = 0; i < N; i++) { depthCopy.push_back({depth[i], i}); } sort(rall(depthCopy)); for (int i = 0; i < N; i++) { if (vis[depthCopy[i].second]) continue; for (int j = i + 1; j < N; j++) { if (vis[depthCopy[j].second]) continue; if (findLCA(depthCopy[i].second, depthCopy[j].second) == center) { vis[depthCopy[i].second] = true; vis[depthCopy[j].second] = true; mx += 2 * (depthCopy[i].first + depthCopy[j].first); swap(ansMax[depthCopy[i].second], ansMax[depthCopy[j].second]); // cerr << "swapping: " << depthCopy[i].second + 1 << " " << depthCopy[j].second + 1 << endl; break; } } } // if (!vis[center]) { // vis[center] = true; // mx += 2; // swap(ansMax[center], ansMax[adj[center][0]]); // } // print the answer cout << mn sp mx << endl; for (int x : ansMin) cout << x + 1 << " "; cout << endl; for (int x : ansMax) cout << x + 1 << " "; cout << endl; return; } signed main() { fast_io(); solution(); // int tests; cin >> tests; // while (tests--) { // solution(); // } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...