Submission #1240788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240788		arman_ferdous	Swapping Cities (APIO20_swap)	C++20	13 / 100	191 ms	38024 KiB

swap

#include "swap.h"
#ifdef DeBuG
#include "debug.h"
#else
#include <bits/stdc++.h>
#define dbg(...)
#endif
using namespace std;

#define sz(v) (int)(v).size()
#define all(v) v.begin(),v.end()
#define rep(i,a,b) for (int i=(a);i<(b);++i)
using ll = long long; using pii = pair<int,int>;
using pll = pair<ll,ll>; using vi = vector<int>;
template<class T> using V = vector<T>;

const int N = 2e5+10;
const int LG = __lg(N) + 1;
const int oo = 2e9;

V<int> g[N];
struct DSU {
    int n;
    V<int> p, sub;
    V<pii> endpoints;

    DSU (int _n = 0) : n(_n), p(n), sub(n), endpoints(n) {
        p.reserve(n + n); sub.reserve(n + n); endpoints.reserve(n + n);
        for (int i = 0; i < n; ++i)
            p[i] = i, sub[i] = oo,
            endpoints[i] = {i, i};
    }

    int find (int u) {
        if (p[u] == u) return u;
        return p[u] = find(p[u]);
    }

    bool endpoints_merge (int u, int v, int U, int V) {
        if (u != endpoints[U].first && u != endpoints[U].second) return false;
        if (v != endpoints[V].first && v != endpoints[V].second) return false;
        return true;
    }

    void merge (int u, int v, int w) {
        int U = find(u), V = find(v);

        if (U == V) {
            endpoints[U].first = endpoints[U].second = -1;
            sub[U] = min(sub[U], w);
            return;
        }

        g[n].push_back(U); g[n].push_back(V);

        if (endpoints_merge(u, v, U, V)) {
            p.push_back(n);
            sub.push_back(oo);
            endpoints.emplace_back(endpoints[V].first ^ endpoints[V].second ^ v,
                                   endpoints[U].first ^ endpoints[U].second ^ u);
        }
        else {
            p.push_back(n);
            sub.push_back(w);
            endpoints.emplace_back(-1, -1);
        }
        p[U] = p[V] = n++;
    }
}dsu;

int n, m;
int lev[N], jmp[LG][N];

void dfs (int u) {
    for (int v : g[u]) {
        lev[v] = lev[u] + 1;
        jmp[0][v] = u;
        for (int j = 1; j < LG; ++j) jmp[j][v] = jmp[j - 1][jmp[j - 1][v]];
        dfs(v);
    }
}

int lca (int u, int v) {
    if (lev[u] > lev[v]) swap(u, v);
    for (int j = LG - 1; j >= 0; --j)
        if (lev[v] - (1 << j) >= lev[u])
            v = jmp[j][v];
    if (u == v) return u;
    for (int j = LG - 1; j >= 0; --j)
        if (jmp[j][u] != jmp[j][v])
            u = jmp[j][u], v = jmp[j][v];
    return jmp[0][u];
}

void init(int _N, int _M, vector<int> u, vector<int> v, vector<int> w) {
    n = _N, m = _M;
    dsu = DSU(n);

    V<int> ord(m); iota(all(ord), 0);
    sort(all(ord), [&](int i, int j) { return w[i] < w[j]; });
    for (int i : ord) dsu.merge(u[i], v[i], w[i]);

    for (int j = 0; j < LG; ++j) jmp[j][dsu.n - 1] = dsu.n - 1;
    dfs(dsu.n - 1);
}

int getMinimumFuelCapacity(int X, int Y) {
    int u = lca(X, Y);
    if (dsu.endpoints[u].first != -1) {
        for (int j = LG - 1; j >= 0; --j) {
            if (dsu.endpoints[jmp[j][u]].first != -1)
                u = jmp[j][u];
        }
        int ans = oo, v = dsu.p[u];
        if (v != u && dsu.endpoints[v].first == -1) ans = min(ans, dsu.sub[v]);
        if (ans == oo) ans = -1;
        return ans;
    }
    int ans = dsu.sub[u];
    if (ans == oo) return -1;
    return ans;
}

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