Submission #1160172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160172		countless	Village (BOI20_village)	C++20	100 / 100	88 ms	26308 KiB

Village

#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;
ll mn = 0, mx = 0;
vector<int> ansMin, ansMax, depth, subtSz;
unordered_map<int, set<int>> subt;

int getSubtrSz(int node, vector<vector<int>> &adj, int parent = -1) {
	int &res = subtSz[node];
	res = 1;
	for (int i : adj[node]) {
		if (i == parent) { continue; }
		res += getSubtrSz(i, adj, node);
	}
	return res;
}

int getCentroid(int node, vector<vector<int>> &adj, int parent = -1) {
	for (int i : adj[node]) {
		if (i == parent) { continue; }

		if (subtSz[i] * 2 > N) { return getCentroid(i, adj, node); }
	}
	return node;
}

void findDepth(int node, int parent, int sub, int dep, vector<vector<int>> &adj, vector<int> &depth) {
    if (sub == -2) sub = -1;
    else if (sub == -1) sub = node;
    subt[sub].insert(node);

    depth[node] = dep;
    for (auto neighbor : adj[node]) {
        if (neighbor == parent) continue;
        findDepth(neighbor, node, sub, 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]) {
                continue;
            }

            if (vis[neighbor]) continue;
            
            vis[neighbor] = true;
            mn += 2;
            swap(ansMin[parent], ansMin[neighbor]);
        }
    }

    return;
}

void solution() {
    cin >> N;
    ansMin.resize(N), ansMax.resize(N), depth.resize(N), subtSz.resize(N);

    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);
    }

    getSubtrSz(0, adj);
    int centroid = getCentroid(0, adj);
    findDepth(centroid, -1, -2, 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
    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));

    priority_queue<pair<int, int>> pq;

    for (auto x : adj[centroid]) {
        pq.push({subt[x].size(), x});
    }

    // pair subtrees together
    bool flag = false;
    while (!pq.empty()) {
        pair<int, int> fir = pq.top(); pq.pop();
        if (pq.empty()) {flag = true; pq.push(fir); break;}
        pair<int, int> sec = pq.top(); pq.pop();

        auto ele1 = subt[fir.second].begin(), ele2 = subt[sec.second].begin();
        swap(ansMax[*ele1], ansMax[*ele2]);
        mx += depth[*ele1] + depth[*ele2];

        subt[fir.second].erase(ele1);
        subt[sec.second].erase(ele2);

        fir.first--; sec.first--;
        if (fir.first > 0) pq.push(fir);
        if (sec.first > 0) pq.push(sec);
    }


    if (flag) {
        auto ele1 = subt[pq.top().second].begin(); int ele2 = centroid;
        swap(ansMax[*ele1], ansMax[ele2]);
        mx += depth[*ele1] + depth[ele2];
    } else {
        swap(ansMax[centroid], ansMax[adj[centroid][0]]);
    }

    // print the answer
    cout << mn sp mx * 2 << 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();

    return 0;
}

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