Submission #1219186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219186		Mans21	Swapping Cities (APIO20_swap)	C++20	100 / 100	965 ms	59028 KiB

swap

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

using namespace std;
const int maxn = 100'000 + 12;

vector<pair<int, int>> g[maxn], t[maxn], e[maxn];
int up[20][maxn], mx[20][maxn], mn[20][maxn];
int p[maxn], d[maxn], dist[maxn];
int n, m;

int get(int x) {
    if(p[x] == x) return x;
    return p[x] = get(p[x]);
}

void dfs(int v, int p, int w) {
    up[0][v] = p;
    mx[0][v] = w;

    for(auto [to, c] : t[v]) {
        if(to == p) {
            continue;
        }
        e[v].push_back({to, c});
    }

    mn[0][v] = 2e9;
    if(e[v].size() >= 2) {
        mn[0][v] = e[v][1].second;
    }

    for(int i = 1; i < 20; i++) {
        up[i][v] = up[i - 1][up[i - 1][v]];
        mx[i][v] = max(mx[i - 1][v], mx[i - 1][up[i - 1][v]]);
        mn[i][v] = min(mn[i - 1][v], mn[i - 1][up[i - 1][v]]);
    }

    for(auto [to, c] : g[v]) {
        if(to != p) {
            d[to] = d[v] + 1;
            dfs(to, v, c);
        }
    }
}

int get(int u, int v) {
    int ansMx = 0, ansMn = min(dist[u], dist[v]);
    if(d[u] < d[v]) {
        swap(u, v);
    }

    for(int i = 19; i >= 0; i--) {
        if(d[u] - d[v] >= (1 << i)) {
            ansMx = max(ansMx, mx[i][u]);
            ansMn = min(ansMn, mn[i][u]);
            u = up[i][u];
        }
    }

    if(u == v) {
        return max(ansMx, ansMn);
    }

    for(int i = 19; i >= 0; i--) {
        if(up[i][u] != up[i][v]) {
            ansMx = max({ansMx, mx[i][u], mx[i][v]});
            ansMn = min({ansMn, mn[i][u], mn[i][v]});
            u = up[i][u], v = up[i][v];
        }
    }

    ansMx = max({ansMx, mx[0][u], mx[0][v]});
    u = up[0][u];
    if(t[u].size() > 2) {
        ansMn = min(ansMn, t[u][2].second);
    }
    return max(ansMx, ansMn);
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {

    n = N, m = M;
    vector<array<int, 3>> edge;
    for(int i = 0; i < m; i++) {
        t[U[i]].push_back({V[i], W[i]});
        t[V[i]].push_back({U[i], W[i]});
        edge.push_back({U[i], V[i], W[i]});
    }
    for(int i = 0; i < n; i++) {
        p[i] = i;
        dist[i] = 2e9;
        sort(t[i].begin(), t[i].end(), [](pair<int, int> x, pair<int, int> y) {
            return x.second < y.second;
        });
        if(t[i].size() >= 3) {
            dist[i] = t[i][2].second;
        }
    }

    sort(edge.begin(), edge.end(), [](array<int, 3> x, array<int, 3> y) {
        return x[2] < y[2];
    });

    for(auto [u, v, w] : edge) {
        if(get(u) != get(v)) {
            p[get(u)] = get(v);
            g[v].push_back({u, w});
            g[u].push_back({v, w});
        }
        else {
            dist[u] = min(dist[u], w);
        }
    }

    set<pair<int, int>> s;
    for(int i = 0; i < n; i++) {
        s.insert({dist[i], i});
    }
    while(!s.empty()) {
        int v = s.begin() -> second;
        s.erase(s.begin());
        for(auto [to, w] : t[v]) {
            if(max(dist[v], w) < dist[to]) {
                s.erase({dist[to], to});
                dist[to] = max(dist[v], w);
                s.insert({dist[to], to});
            }
        }
    }

    dfs(0, 0, 0);
}

int getMinimumFuelCapacity(int X, int Y) {
    if(get(X, Y) > 1e9) {
        return -1;
    }
    return get(X, Y);
}

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