Submission #932305

#	Time	Username	Problem	Language	Result	Execution time	Memory
932305		amirhoseinfar1385	Village (BOI20_village)	C++17	100 / 100	76 ms	27288 KiB

Village

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 100'000;

int n;
int resMin[N + 10], ansMin;
int resMax[N + 10], root, cnt, sz[N + 10];
vector<int> base[N + 10], vec[N + 10], res[N + 10];
vector<int> adj[N + 10];
ll ansMax;

void readInput() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

void calcSz(int u = 1, int par = 0) {
    sz[u] = 1;
    for (auto v: adj[u])
        if (v != par) {
            calcSz(v, u);
            sz[u] += sz[v];
        }
    ansMax += (ll) min(sz[u], n - sz[u]) * 2ll;
}

int getCentroid() {
    int res = 1;
    while (true) {
        int ok = res;
        for (auto v: adj[res])
            if (sz[v] < sz[res] && sz[v] > n / 2)
                ok = v;
        if (ok == res)
            return res;
        res = ok;
    }
}

void addBase(int u, int par) {
    base[cnt].push_back(u);
    for (auto v: adj[u])
        if (v != par)
            addBase(v, u);
}

void calcBase(int root) {
    base[++cnt].push_back(root);
    vec[cnt] = base[cnt];
    for (auto u: adj[root]) {
        cnt++;
        addBase(u, root);
        vec[cnt] = base[cnt];
    }
}

void calcResVectors() {
    set<pair<int, int>> st;
    for (int i = 1; i <= cnt; i++)
        st.insert({base[i].size(), i});
    while (st.size() >= 2) {
        int idx1 = st.rbegin() -> second;
        st.erase(*st.rbegin());
        int idx2 = st.rbegin() -> second;
        st.erase(*st.rbegin());
        int ver1 = vec[idx1].back(), ver2 = vec[idx2].back();
        res[idx1].push_back(ver2);
        res[idx2].push_back(ver1);
        vec[idx1].pop_back();
        vec[idx2].pop_back();
        if (vec[idx1].size())
            st.insert({vec[idx1].size(), idx1});
        if (vec[idx2].size())
            st.insert({vec[idx2].size(), idx2});
    }
    if (st.size()) {
        res[1].push_back(base[1][0]);
        swap(res[2].back(), res[1].back());
    }
}

void calcResMax() {
    for (int i = 1; i <= cnt; i++)
        for (int j = 0; j < base[i].size(); j++)
            resMax[base[i][j]] = res[i][j];
}

void solveMax() {
    calcSz();
    root = getCentroid();
    calcBase(root);
    calcResVectors();
    calcResMax();
}

int dfs(int u = 1, int par = 0) {
    vector<int> vec;
    for (auto v: adj[u])
        if (v != par) {
            int x = dfs(v, u);
            if (x)
                vec.push_back(x);
        }
    while (vec.size() > 2) {
        int ver1 = vec.back();
        vec.pop_back();
        int ver2 = vec.back();
        vec.pop_back();
        swap(resMin[ver1], resMin[ver2]);
        ansMin += 4;
    }
    if (vec.size() == 1) {
        swap(resMin[u], resMin[vec[0]]);
        ansMin += 2;
        return 0;
    }
    if (vec.size() == 0 && u != 1)
        return u;
    if (vec.size()) {
        int b1 = vec[0], b2 = vec[1];
        swap(resMin[u], resMin[b1]);
        swap(resMin[u], resMin[b2]);
        ansMin += 4;
    }
    else {
        swap(resMin[1], resMin[adj[u][0]]);
        ansMin += 2;
    }
    return 0;
}

void solveMin() {
    for (int i = 1; i <= n; i++)
        resMin[i] = i;
    dfs();
}

void writeOutput() {
    cout << ansMin << ' ' << ansMax << '\n';
    for (int i = 1; i <= n; i++)
        cout << resMin[i] << ' ';
    cout << '\n';
    for (int i = 1; i <= n; i++)
        cout << resMax[i] << ' ';
    cout.flush();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    if (n == 1) {
        cout << 0 << ' ' << 0 << '\n';
        cout << 1 << '\n' << 1;
        cout.flush();
        return 0;
    }
    solveMax();
    solveMin();
    writeOutput();
    return 0;   
}

Compilation message (stderr)

Village.cpp: In function 'void calcResMax()':
Village.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int j = 0; j < base[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~

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