Submission #402067

#	Time	Username	Problem	Language	Result	Execution time	Memory
402067		KoD	Swapping Cities (APIO20_swap)	C++17	100 / 100	330 ms	16220 KiB

swap

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

template <class T>
using Vec = std::vector<T>;

constexpr int INF = 1000000000 + 5;

struct DSU {
    int cur;
    Vec<int> date, par;
    DSU() = default;
    DSU(const int n): cur(0), date(n, INF), par(n, -1) { }

    int find(int u, const int t) const {
        while (date[u] < t) u = par[u];
        return u;
    }

    void merge(int u, int v) {
        u = find(u, cur);
        v = find(v, cur);
        cur += 1;
        if (u == v) return;
        if (par[u] > par[v]) {
            std::swap(u, v);
        }
        par[u] += par[v];
        par[v] = u;
        date[v] = cur - 1;
    }

    int when(const int u, const int v) const {
        if (u == v) return 0;
        if (find(u, cur) != find(v, cur)) return INF;
        int ok = cur, ng = 0;
        while (ok - ng > 1) {
            const int md = (ok + ng) / 2;
            (find(u, md) == find(v, md) ? ok : ng) = md;
        }
        return ok;
    }
};

DSU dsu;
Vec<int> par, cost, date;

void init(int N, int M, Vec<int> U, Vec<int> V, Vec<int> W) {
    Vec<int> order(M);
    std::iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(), [&](const int i, const int j) {
        return W[i] < W[j];
    });
    par = Vec<int>(N, -1);
    date = Vec<int>(N, INF);
    Vec<int> deg(N, 0);
    dsu = DSU(N);
    cost.reserve(M);
    const auto find = [&](int u) {
        while (par[u] >= 0) u = par[u];
        return u;
    };
    for (const auto i: order) {
        deg[U[i]] += 1;
        deg[V[i]] += 1;
        const bool f = deg[U[i]] > 2 or deg[V[i]] > 2;
        int u = find(U[i]);
        int v = find(V[i]);
        if (u == v) {
            if (date[u] == INF) {
                date[u] = W[i];
            }
        }
        else {
            if (par[u] > par[v]) {
                std::swap(u, v);
            }
            par[u] += par[v];
            par[v] = u;
            if (date[u] == INF and (date[v] != INF or f)) {
                date[u] = W[i];
            }
            if (date[v] == INF and (date[u] != INF or f)) {
                date[v] = W[i];
            }
        }
        dsu.merge(U[i], V[i]);
        cost.push_back(W[i]);
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    int ret = cost[dsu.when(X, Y) - 1];
    while (par[X] >= 0 and date[X] == INF) {
        X = par[X];
    }
    while (par[Y] >= 0 and date[Y] == INF) {
        Y = par[Y];
    }
    ret = std::max(ret, std::min(date[X], date[Y]));
    return ret == INF ? -1: ret;
}

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