Submission #948809

#	Time	Username	Problem	Language	Result	Execution time	Memory
948809		lolismek	Village (BOI20_village)	C++14	50 / 100	61 ms	16328 KiB

Village

#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){
    for(int vec : adj[node]){
        if(vec != par){
            dfs3(vec, node);
        }
    }
    aux.pb(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;
    }
 
    dfs3(centroid, 0);
 
    for(int i = 0; i < n / 2; i++){
        swap(max_pos[aux[i]], max_pos[aux[n / 2 + i]]);
    }
    // if(max_pos[centroid] == centroid){
    //     swap(max_pos[centroid], max_pos[adj[centroid][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
 
 
*/

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50