Submission #392512

#	Time	Username	Problem	Language	Result	Execution time	Memory
392512		arujbansal	Swapping Cities (APIO20_swap)	C++17	100 / 100	382 ms	96528 KiB

swap

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>
#include "swap.h"

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long

struct LCA {
    int n, k;
    vector<vector<int>> adj, sparse_table;
    vector<int> euler, first_occurrence;
    int timer;
    bool lca_built;

    LCA(int _n = 0) { 
        lca_built = false;

        if (_n > 0)
            init(_n);
    }

    void init(int _n) {
        lca_built = false;

        n = _n;

        adj.resize(n);
        for (int i = 0; i < n; i++)
            adj[i].clear();

        euler.clear();
        first_occurrence.resize(n);
        timer = 0;
    }

    void add_edge(int u, int v) {
        assert(n > 0);

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void run(int root = 0) {
        assert(n > 0);

        dfs(root, -1);
        build();

        lca_built = true;
    }

    void dfs(int u = 0, int p = -1) {
        first_occurrence[u] = timer++;
        euler.push_back(u);

        for (const auto &v : adj[u]) {
            if (v == p) continue;
            
            dfs(v, u);
            euler.push_back(u);
            timer++;
        }
    }

    void build() {
        k = 31 - __builtin_clz(timer) + 1;

        sparse_table.resize(k);

        for (int i = 0; i < k; i++)
            sparse_table[i].resize(timer - (1 << i) + 1);

        for (int j = 0; j < timer; j++)
            sparse_table[0][j] = euler[j];

        for (int i = 1; i < k; i++) {
            for (int j = 0; j + (1 << i) - 1 < timer; j++) {
                int x = sparse_table[i - 1][j];
                int y = sparse_table[i - 1][j + (1 << (i - 1))];

                sparse_table[i][j] = (first_occurrence[x] < first_occurrence[y] ? x : y);
            }
        }
    }

    int query(int u, int v) {
        assert(lca_built == true);

        int l = first_occurrence[u], r = first_occurrence[v];
        if (l > r)
            swap(l, r);

        int i = 31 - __builtin_clz(r - l + 1);

        int x = sparse_table[i][l], y = sparse_table[i][r - (1 << i) + 1];
        return first_occurrence[x] < first_occurrence[y] ? x : y;
    }
};

const int MXN = 5e5 + 5, INF = 1e9 + 5;
int par[MXN], degree[MXN], valid[MXN], cost[MXN];
int fake_node;
vector<array<int, 3>> edges;
LCA reach_lca;

int find_par(int x) {
    if (par[x] == x) return x;
    return par[x] = find_par(par[x]);
}

void unite(int u, int v, int w) {
    degree[u]++;
    degree[v]++;

    valid[fake_node] |= (degree[u] >= 3) | (degree[v] >= 3);

    u = find_par(u), v = find_par(v);

    par[u] = fake_node;
    par[v] = fake_node;

    valid[fake_node] |= valid[u] | valid[v];
    if (valid[fake_node])
        cost[fake_node] = w;
    
    if (u == v) {
        valid[fake_node] = 1;
        cost[fake_node] = w;
        reach_lca.add_edge(fake_node++, u);

        return;
    }

    reach_lca.add_edge(fake_node, u);
    reach_lca.add_edge(fake_node, v);

    fake_node++;
}

void dfs(int u, int p) {
    for (const auto &v : reach_lca.adj[u]) {
        if (v == p) continue;
        cost[v] = min(cost[v], cost[u]);

        dfs(v, u);
    }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < M; i++)
        edges.emplace_back(array<int, 3>{U[i], V[i], W[i]});

    sort(all(edges), [&](const array<int, 3> &x, const array<int, 3> &y) { return x[2] < y[2]; });

    fake_node = N;

    for (int i = 0; i < MXN; i++) {
        cost[i] = INF;
        par[i] = i;
    }

    reach_lca.init(MXN);

    for (const auto &[u, v, w] : edges)
        unite(u, v, w);

    for (int i = 0; i < fake_node; i++) {
        if (par[i] == i) {
            reach_lca.add_edge(i, fake_node + 1);
        }
    }

    fake_node++;
    reach_lca.run(fake_node);
    dfs(fake_node, -1);
}

int getMinimumFuelCapacity(int X, int Y) {
    int ans = cost[reach_lca.query(X, Y)];
    return (ans < INF ? ans : -1);
}

#ifdef local
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<int> U(M), V(M), W(M);

    for (int i = 0; i < M; i++)
        cin >> U[i] >> V[i] >> W[i];

    init(N, M, U, V, W);

    int Q;
    cin >> Q;

    while (Q--) {
        int X, Y;
        cin >> X >> Y;

        cout << getMinimumFuelCapacity(X, Y) << "\n";
    }
}
#endif

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