Submission #1193555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193555		omsincoconut	Swapping Cities (APIO20_swap)	C++17	7 / 100	191 ms	47372 KiB

swap

/*
Find minimum spanning tree
Answer is the max of these three things
- Path max from u to v
- Minimum of third adjacent minimums from u to v
*/

#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+5;
const int INF = 2e9;

struct DSU{
    int p[MAXN], sz[MAXN];

    void init() {
        for (int i = 0; i < MAXN; i++) {
            p[i] = i;
            sz[i] = 1;
        }
    }

    int find_set(int u) {
        vector<int> chain = {u};
        while (p[chain.back()] != chain.back()) {
            chain.push_back(p[chain.back()]);
        }

        int ret = chain.back();
        for (int i : chain) p[i] = ret;
        return ret;
    }

    bool merge_set(int u, int v) {
        u = find_set(u); v = find_set(v);
        if (u == v) return false;
        if (sz[u] < sz[v]) swap(u, v);
        p[v] = u;
        sz[u] += sz[v];
        return true;
    }
} dsu;

vector<pair<int, int>> edge[MAXN];

int depth[MAXN], p[20][MAXN], pc[20][MAXN], p3[20][MAXN];

void dfs(int u) {
    for (auto [v, w] : edge[u]) {
        if (depth[v] != -1) continue;
        depth[v] = depth[u] + 1;
        p[0][v] = u;
        pc[0][v] = w;
        dfs(v);
    }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    dsu.init();
    tuple<int, int, int> edge_list[M];
    for (int i = 0; i < M; i++) {
        edge_list[i] = make_tuple(W[i], U[i], V[i]);
    }

    sort(edge_list, edge_list+M);
    vector<int> adj_weight[N];
    for (int i = 0; i < M; i++) {
        int w, u, v;
        tie(w, u, v) = edge_list[i];
        if (dsu.merge_set(u, v)) {
            edge[u].emplace_back(v, w);
            edge[v].emplace_back(u, w);
        }

        adj_weight[u].push_back(w);
        adj_weight[v].push_back(w);
    }

    fill(depth, depth+N, -1);
    depth[0] = p[0][0] = pc[0][0] = 0;
    dfs(0);

    for (int i = 0; i < N; i++) {
        p3[0][i] = (adj_weight[i].size() >= 3 ? adj_weight[i][2] : INF);
    }

    for (int j = 1; j <= 19; j++) {
        for (int i = 0; i < N; i++) {
            p[j][i] = p[j-1][p[j-1][i]];
            pc[j][i] = max(pc[j-1][i], pc[j-1][p[j-1][i]]);
            p3[j][i] = min(p3[j-1][i], p3[j-1][p[j-1][i]]);
        }
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    int ret1 = 0;
    int ret2 = INF;

    if (depth[X] < depth[Y]) swap(X, Y);

    int delta_depth = depth[X] - depth[Y];
    for (int j = 19; j >= 0; j--) {
        if (delta_depth&(1<<j)) {
            ret1 = max(ret1, pc[j][X]);
            ret2 = min(ret2, p3[j][X]);
            X = p[j][X];
        }
    }

    if (X == Y) {
        ret2 = min(ret2, p3[0][X]);
        return max(ret1, ret2) >= INF ? -1 : max(ret1, ret2);
    }

    for (int j = 19; j >= 0; j--) {
        if (p[j][X] != p[j][Y]) {
            ret1 = max({ret1, pc[j][X], pc[j][Y]});
            ret2 = min({ret2, p3[j][X], p3[j][Y]});
            X = p[j][X];
            Y = p[j][Y];
        }
    }

    ret1 = max({ret1, pc[0][X], pc[0][Y]});
    ret2 = min({ret2, p3[0][X], p3[0][Y], p3[0][p[0][X]]});

    return max(ret1, ret2) >= INF ? -1 : max(ret1, ret2);
}

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27