Submission #1123719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123719		anmattroi	Swapping Cities (APIO20_swap)	C++20	100 / 100	357 ms	129032 KiB

swap

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

using namespace std;

#define fi first
#define se second

using ii = pair<int, int>;

int pos[maxn], val[maxn], id = 0;
ii f[20][maxn+maxn];

int LCA(int u, int v) {
    u = pos[u]; v = pos[v];
    if (u > v) swap(u, v);
    int k = __lg(v-u+1);
    return min(f[k][u], f[k][v-(1<<k)+1]).se;
}

int LCP(int u, int v) {
    if (u > v) swap(u, v);
    int k = __lg(v-u+1);
    return min(f[k][u], f[k][v-(1<<k)+1]).se;
}

set<int> nho;

void init(int N, int M,
    vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < M; i++) {++U[i]; ++V[i];}
    struct edge {
        int u, v, l;
        edge() {}
        edge(int _u, int _v, int _l) : u(_u), v(_v), l(_l) {}

        bool operator < (const edge &other) const {
            return l < other.l;
        }
    } edges[M+1];

    for (int i = 0; i < M; i++) edges[i+1] = edge(U[i], V[i], W[i]);

    sort(edges + 1, edges + M + 1);

    int lt[N+1], deg[N+1], flag[N+1], maxdeg[N+1];

    for (int i = 1; i <= N; i++) {
        lt[i] = i;
        deg[i] = flag[i] = maxdeg[i] = 0;
    }

    function<int(int)> found_set = [&](int v) {
        return lt[v] == v ? v : lt[v] = found_set(lt[v]);
    };

    function<void(int, int)> onion_set = [&](int u, int v) {
        int a = ++deg[u], b = ++deg[v];
        u = found_set(u); v = found_set(v);
        if (u == v) {
            flag[u] = 1;
            maxdeg[u] = max({maxdeg[u], a, b});
            return;
        }
        lt[u] = v;
        flag[v] |= flag[u];
        maxdeg[v] = max({maxdeg[v], a, b});
    };

    int par[N+M+1], good[N+M+1];
    fill(good + 1, good + N + M + 1, 0);
    iota(par + 1, par + N + M + 1, 1);

    function<int(int)> find_set = [&](int v) {return par[v] == v ? v : par[v] = find_set(par[v]);};

    int root = N;

    vector<int> adj[N+M+1];

    for (int i = 1; i <= M; i++) {
        auto [u, v, l] = edges[i];
        onion_set(u, v);
        int w = found_set(u);
        ++root;
        if (flag[w] || maxdeg[w] >= 3) good[root] = 1;
        u = find_set(u); v = find_set(v);
        val[root] = l;
        adj[root].emplace_back(u);
        if (u != v) adj[root].emplace_back(v);
        par[u] = par[v] = root;
    }

    int d[N+M+1];

    function<void(int)> dfs = [&](int u) {
        f[0][++id] = {d[u], u};
        pos[u] = id;
        if (good[u]) nho.insert(id);
        for (int v : adj[u]) {
            d[v] = d[u] + 1;
            dfs(v);
            f[0][++id] = {d[u], u};
        }
    };
    d[root] = 0;
    dfs(root);
    for (int i = 1; (1<<i) <= id; i++) for (int j = 1; j + (1<<i) - 1 <= id; j++) f[i][j] = min(f[i-1][j], f[i-1][j+(1<<(i-1))]);

}

int getMinimumFuelCapacity(int X, int Y) {
    ++X; ++Y;
    if (nho.size() == 0) return -1;
    int p = LCA(X, Y);
    int u = pos[p];
    auto it = nho.lower_bound(u);
    int ans = INT_MAX;
    if (it != nho.end()) {
        ans = min(ans, val[LCP(u, *it)]);
    }
    if (it != nho.begin()) {
        --it;
        ans = min(ans, val[LCP(u, *it)]);
    }
    return ans;
}

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