Submission #743180

#	Time	Username	Problem	Language	Result	Execution time	Memory
743180		fanwen	Swapping Cities (APIO20_swap)	C++17	100 / 100	614 ms	46264 KiB

swap

#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()

#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

template <class U, class V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <class U, class V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }
const int MAXN = 1e5 + 5;
int N, M, d[MAXN * 3], lab[MAXN * 3], par[22][MAXN * 3], deg[MAXN], weight[MAXN * 3], jump[MAXN * 3];
vector <int> ke[MAXN * 3];
bool is[MAXN * 3];
int find(int u) { return lab[u] == u ? u : lab[u] = find(lab[u]); }

void merge(int u, int v, int w) {
    deg[u]++, deg[v]++;
    bool More2 = (deg[u] > 2 || deg[v] > 2);
    u = find(u), v = find(v);
    if(u == v) {
        if(is[u] == 0) is[u] = 1, weight[u] = w;
        return;
    } 
    N++;
    lab[u] = lab[v] = N;
    ke[N].push_back(u); ke[N].push_back(v);
    is[N] = (More2 || is[u] || is[v]);
    weight[N] = w;
}

void dfs(int u, int pre) {
    if(is[u]) pre = u;
    jump[u] = pre;
    for (auto v : ke[u]) {
        par[0][v] = u;
        FOR(i, 1, 19) par[i][v] = par[i - 1][par[i - 1][v]];
        d[v] = d[u] + 1;
        dfs(v, pre);
    }
}

int lca(int u, int v) {
    
    if(d[u] < d[v]) swap(u, v);

    FORD(i, 19, 0) if(d[par[i][u]] >= d[v]) {
        u = par[i][u];
    }
    
    if(u == v) return u;

    FORD(i, 19, 0) if(par[i][u] != par[i][v]) {
        u = par[i][u];
        v = par[i][v];
    }
    return par[0][u];
}

void init(int n, int m, vector <int> U, vector <int> V, vector <int> W) {
    N = n, M = m;
    vector <int> idx(m);
    iota(lab, lab + N + M + 1, 0);
    iota(ALL(idx), 0);
    sort(ALL(idx), [&](const int &a, const int &b) { return W[a] < W[b]; });
    for (auto i : idx) {
        merge(U[i] + 1, V[i] + 1, W[i]);
    }
    weight[0] = -1; dfs(N, 0);
}

int getMinimumFuelCapacity(int X, int Y) {
    return weight[jump[lca(X + 1, Y + 1)]];
}

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