제출 #1171620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171620		phungmanager0	Village (BOI20_village)	C++20	0 / 100	1 ms	2628 KiB

Village

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
#define IS_INF(x)   (std::isinf(x))
#define IS_NAN(x)   (std::isnan(x))
#define fi   first
#define se   second
#define int long long
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define div   ___div
#define prev   ___prev
#define next   ___next
#define left   ___leftc
#define right   ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
const int MAXN = 1e5 + 5;
int n, a[MAXN], Sz[MAXN], ans[MAXN], res = 0; vector<int> g[MAXN];
bool del[MAXN]; vector<int> trace;
void loadgraph() {
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
}
void dfs1(int u, int p = -1) {
    Sz[u] = 1;
    del[u] = true;
    trace.push_back(u);
    for(auto x : g[u]) {
        if(x != p && !del[x]) {
            dfs1(x, u);
            Sz[u] += Sz[x];
        }
    }
    res += 2 * min(Sz[u], n - Sz[u]);
}
void dfs(int u, int p = -1) {
    Sz[u] = 1;
    for(auto x : g[u]) {
        if(x != p) {
            dfs(x, u);
            Sz[u] += Sz[x];
        }
    }
}
int FindCentroid(int u, int p = -1) {
    for(auto x : g[u]) {
        if(x != p && Sz[x] > n / 2) {
            return FindCentroid(x, u);
        }
    }
    return u;
}
void CentroidDecomposition() {
    int root = FindCentroid(1);
    del[root] = true;
    trace.push_back(root);
    for(auto x : g[root]) {
        if(!del[x]) {
            dfs1(x, root);
        }
    }
    cout << res << "\n";
    for(int i = 0; i < n; i++) {
        ans[trace[i]] = trace[(i + (n + 1) / 2) % n];
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << " ";
}
main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    loadgraph();
    dfs(1);
    CentroidDecomposition();
    return 0;
}

// Author: Phung Duc Minh
// Look at my code, my code is so amazing and legit
// Try to be better!

컴파일 시 표준 에러 (stderr) 메시지

Village.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main(void) {
      | ^~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50