Submission #1160078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160078		countless	Village (BOI20_village)	C++20	25 / 100	1094 ms	18500 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;
int mn = 0, mx = 0, timer = 0;
vector<int> ansMin, ansMax, depth, tin, tout, par;
vector<vector<int>> up;

// 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];
}

// mem this
int treeCenter(vector<vector<int>> &adj) {
    vector<int> deg(N, 0);
    vector<int> leaves;

    for (int i = 0; i < N; i++) {
        deg[i] = adj[i].size();
        if (deg[i] == 0 || deg[i] == 1) {
            leaves.push_back(i);
            deg[i] = 0;
        }
    }

    int count = leaves.size();
    while (count < N) {
        vector<int> newLeaves;
        for (auto node : leaves) {
            for (auto neighbor : adj[node]) {
                deg[neighbor]--;
                if (deg[neighbor] == 1) {
                    newLeaves.push_back(neighbor);
                }
            }

            deg[node] = 0;
        }

        count += newLeaves.size();
        leaves = newLeaves;
    }

    return leaves[0];
}

void findDepth(int node, int parent, int dep, vector<vector<int>> &adj, vector<int> &depth) {
    depth[node] = dep;
    for (auto neighbor : adj[node]) {
        if (neighbor == parent) continue;
        findDepth(neighbor, node, 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), tin.resize(N), tout.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);
    }

    int center = treeCenter(adj);
    findDepth(center, -1, 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));
    
    for (int i = 0; i < N; i++) {
        if (vis[depthCopy[i].second]) continue;
        for (int j = i + 1; j < N; j++) {
            if (vis[depthCopy[j].second]) continue;
            if (findLCA(depthCopy[i].second, depthCopy[j].second) == center) {
                vis[depthCopy[i].second] = true;
                vis[depthCopy[j].second] = true;
                mx += 2 * (depthCopy[i].first + depthCopy[j].first);
                swap(ansMax[depthCopy[i].second], ansMax[depthCopy[j].second]);
                // cerr << "swapping: " << depthCopy[i].second + 1 << " " << depthCopy[j].second + 1 << endl;
                break;
            }
        }
    }

    // if (!vis[center]) {
    //     vis[center] = true;
    //     mx += 2;
    //     swap(ansMax[center], ansMax[adj[center][0]]);
    // }


    // print the answer
    cout << mn sp mx << 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: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 0 / 50