Submission #1160171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160171		countless	Village (BOI20_village)	C++20	100 / 100	114 ms	36808 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, LOGN;
ll mn = 0, mx = 0, timer = 0;
vector<int> ansMin, ansMax, depth, par;
vector<vector<int>> up;
unordered_map<int, set<int>> subt;
int subtree_size[100005];

// mem this
void binLift(vector<vector<int>> &adj) {
    for (int i = 0; i < N; i++) {
        up[i][0] = par[i];
    }
    
    for (int j = 1; j < LOGN; j++) {
        for (int i = 0; i < N; i++) {
            if (up[i][j - 1] == -1) continue;
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }
}

// mem this
int findLCA(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);

    int diff = depth[u] - depth[v];
    for (int i = 0; i < LOGN; i++) {
        if (diff & (1 << i)) {
            u = up[u][i];
        }
    }

    // one is the ancestor of the other
    if (u == v) {
        return u;
    }

    // find last non-common ancestor
    for (int i = 0; i < LOGN; i++) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }

    return up[u][0];
}

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

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

		if (subtree_size[i] * 2 > N) { return get_centroid(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]) {
                par[parent] = neighbor;
                continue;
            }
            par[neighbor] = parent;

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

    return;
}

void solution() {
    cin >> N; LOGN = ceil(log2(N));
    ansMin.resize(N), ansMax.resize(N), depth.resize(N), par.resize(N);
    up.assign(N, vector<int>(LOGN, -1));

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

    get_subtree_size(0, adj);
    int center = get_centroid(0, adj);
    findDepth(center, -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
    par[center] = -1;
    binLift(adj);

    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[center]) {
        pq.push({subt[x].size(), x});
        // for (auto y : subt[x]) {
        //     cerr << y << " ";
        // }
        // cerr << endl;
    }

    // cerr << pq.top().first << endl;

    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 = center;
        swap(ansMax[*ele1], ansMax[ele2]);
        mx += depth[*ele1] + depth[ele2];
    } else {
        swap(ansMax[center], ansMax[adj[center][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();

    // int tests; cin >> tests;
    // while (tests--) {
    //     solution();
    // }

    return 0;
}

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