Submission #948783

#TimeUsernameProblemLanguageResultExecution timeMemory
948783lolismekVillage (BOI20_village)C++14
50 / 100
66 ms17612 KiB
#include <algorithm> #include <iostream> #include <climits> #include <vector> #include <deque> #include <queue> #include <stack> #include <map> #include <set> #include <iomanip> #include <cassert> #include <random> #include <chrono> // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using ull = unsigned long long; using ll = long long; //#define int __int128 //#define int ll #define pii pair <int, int> #define all(a) (a).begin(), (a).end() #define fr first #define sc second #define pb push_back #define lb lower_bound #define ub upper_bound #define vt vector #define FOR(a, b) for(int i = (a); i <= (b); i++) #define FORr(a, b) for(int i = (a); i >= (b); i--) #define sz(x) (int)(x).size() #define YES cout << "YES\n" #define NO cout << "NO\n" using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rangerng(int l, int r){ return uniform_int_distribution<>(l, r)(rng); } //////////////////////////////////////////////////////////////////////////////////// const int NMAX = 1e5; int n; vt <int> adj[NMAX + 1]; int minAns = 0; int min_pos[NMAX + 1]; void dfs1(int node, int par){ for(int vec : adj[node]){ if(vec != par){ dfs1(vec, node); } } if(min_pos[node] == node && node != 1){ swap(min_pos[node], min_pos[par]); minAns += 2; } } int maxAns = 0; int max_pos[NMAX + 1]; int big[NMAX + 1]; void dfs2(int node, int par){ big[node] = 1; for(int vec : adj[node]){ if(vec != par){ dfs2(vec, node); big[node] += big[vec]; } } maxAns += min(big[node], n - big[node]); } int get_centroid(int node, int par){ for(int vec : adj[node]){ if(vec != par && big[vec] > n / 2){ return get_centroid(vec, node); } } return node; } vt <int> aux; void dfs3(int node, int par){ aux.pb(node); for(int vec : adj[node]){ if(vec != par){ dfs3(vec, node); } } } void solve(){ cin >> n; for(int i = 1; i <= n - 1; i++){ int a, b; cin >> a >> b; adj[a].pb(b); adj[b].pb(a); } for(int i = 1; i <= n; i++){ min_pos[i] = i; } dfs1(1, 0); if(min_pos[1] == 1){ int x = adj[1][0]; swap(min_pos[x], min_pos[1]); minAns += 2; } dfs2(1, 0); int centroid = get_centroid(1, 0); for(int i = 1; i <= n; i++){ max_pos[i] = i; } vt <vt <int>> comps; for(int vec : adj[centroid]){ aux.clear(); dfs3(vec, centroid); comps.pb(aux); } comps.pb({centroid}); for(int i = 0; i + 1 < sz(comps); i++){ while(sz(comps[i]) > 0 && sz(comps[i + 1]) > 0){ swap(max_pos[comps[i].back()], max_pos[comps[i + 1].back()]); comps[i].pop_back(); comps[i + 1].pop_back(); } if(sz(comps[i]) > 0){ swap(comps[i], comps[i + 1]); } } //assert(sz(comps.back()) == 0); cout << minAns << ' ' << 2 * maxAns << '\n'; for(int i = 1; i <= n; i++){ cout << min_pos[i] << ' '; } cout << '\n'; for(int i = 1; i <= n; i++){ cout << max_pos[i] << ' '; } cout << '\n'; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int T; //cin >> T; T = 1; while(T--){ solve(); } return 0; } /* 4 1 2 2 3 3 4 7 4 2 5 7 3 4 6 3 1 3 4 5 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...