Submission #1161828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161828		The_Samurai	Swapping Cities (APIO20_swap)	C++20	100 / 100	308 ms	41116 KiB

swap

#include "swap.h"
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second

struct dsu {
    vector<int> p, size;

    void init(int n) {
        size.assign(n, 1);
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }

    int get(int a) {
        return p[a] == a ? a : p[a] = get(p[a]);
    }

    void merge(int a, int b) {
        a = get(a); b = get(b);
        if (a == b) return;
        if (size[a] > size[b]) swap(a, b);
        size[b] += size[a];
        p[a] = b;
    }
};

const int inf = 2e9, lg = 17, N = 1e5 + 5;
vector<int> needs(N, inf);
vector<vector<pair<int, int>>> g(N);
vector jump(lg, vector(N, make_pair(-1, 0)));
vector<int> tin(N), tout(N);
int n, z;

void dfs(int u) {
    for (int i = 1; i < lg and u; i++) {
        jump[i][u].ff = jump[i - 1][jump[i - 1][u].ff].ff;
        if (jump[i][u].ff == -1) break;
        jump[i][u].ss = max(jump[i - 1][u].ss, jump[i - 1][jump[i - 1][u].ff].ss);
    }
    tin[u] = ++z;
    for (auto [v, w]: g[u]) {
        if (tin[v]) continue;
        jump[0][v] = make_pair(u, w);
        dfs(v);
    }
    tout[u] = ++z;
}

bool isPar(int u, int v) { return tin[u] <= tin[v] and tout[v] <= tout[u]; }

int lca(int u, int v) {
    if (isPar(u, v)) return u;
    if (isPar(v, u)) return v;
    for (int i = lg - 1; i >= 0; i--) {
        if (jump[i][u].ff != -1 and !isPar(jump[i][u].ff, v)) {
            u = jump[i][u].ff;
        }
    }
    return jump[0][u].ff;
}

int dist(int u, int v) {
    int p = lca(u, v), res = 0;
    for (int i = lg - 1; i >= 0; i--) {
        if (jump[i][u].ff != -1 and isPar(p, jump[i][u].ff)) {
            res = max(res, jump[i][u].ss);
            u = jump[i][u].ff;
        }
        if (jump[i][v].ff != -1 and isPar(p, jump[i][v].ff)) {
            res = max(res, jump[i][v].ss);
            v = jump[i][v].ff;
        }
    }
    assert(u == p and v == p);
    return res;
}

void init(int _n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = _n;
    vector<pair<int, int>> vec(m);
    vector<int> cnt(n), p(n);
    vector<bool> bad(n);
    vector<vector<int>> child(n);

    for (int i = 0; i < n; i++) {
        child[i] = {i};
        p[i] = i;
    }

    for (int i = 0; i < m; i++) vec[i] = make_pair(W[i], i);
    sort(vec.begin(), vec.end());
    
    for (auto [w, i]: vec) {
        cnt[U[i]]++, cnt[V[i]]++;
        bool now = (cnt[U[i]] > 2) | (cnt[V[i]] > 2);
        int u = p[U[i]], v = p[V[i]];
        if (u == v) {
            if (bad[u]) continue;
            bad[u] = true;
            for (int x: child[u]) needs[x] = w;
            continue;
        }
        // cout << U[i] << ' ' << V[i] << ' ' << w << endl;
        g[U[i]].emplace_back(V[i], w);
        g[V[i]].emplace_back(U[i], w);

        now |= bad[u] | bad[v];
        if (now and !bad[u]) for (int x: child[u]) needs[x] = w;
        if (now and !bad[v]) for (int x: child[v]) needs[x] = w;

        if (child[u].size() > child[v].size()) swap(u, v);
        for (int x: child[u]) {
            child[v].emplace_back(x);
            p[x] = v;
        }
        child[u].clear();
        bad[v] = now;
    }
    dfs(0);
}

int getMinimumFuelCapacity(int x, int y) {
    int ans = max(needs[x], needs[y]);
    ans = max(ans, dist(x, y));
    return ans == inf ? -1 : 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