Submission #1200929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200929		Braabebo10	Swapping Cities (APIO20_swap)	C++20	30 / 100	1746 ms	589824 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
vector<vector<array<ll, 3> > > adj;
vector<vector<ll> > anc, ans, ans2;
vector<ll> w, dep, cost, cost2, dist;
ll n, m, LOG = 20;

array<ll, 3> jump(ll u, ll k) {
    ll res1 = 0, res2 = 0;
    for (ll pw = 0; pw < LOG; pw++)
        if (k >> pw & 1)
            res1 = max(res1, ans[pw][u]), res2 = max(res2, ans2[pw][u]), u = anc[pw][u];
    return {u, res1, res2};
}

array<ll, 3> lca(ll u, ll v) {
    if (dep[u] < dep[v])swap(u, v);
    auto [nxt, res1, res2] = jump(u, max(0LL, dep[u] - dep[v] - 1));
    if (anc[0][nxt] == v)return {anc[0][nxt], max(res1, cost[nxt]), max(res2, ans2[0][nxt])};
    auto [nxt2, r1, r2] = jump(u, dep[u] - dep[v]);
    u = nxt2, res1 = r1, res2 = r2;
    bool enter = 0;
    for (ll pw = LOG - 1; pw >= 0; pw--)
        if (anc[pw][u] != anc[pw][v]) {
            res1 = max({res1, ans[pw][u], ans[pw][v]});
            res2 = max({res2, ans2[pw][u], ans2[pw][v]});
            u = anc[pw][u], v = anc[pw][v];
            enter = 1;
        }
    res1 = max({res1, cost[u], cost[v]});
    res2 = max({res2, ans2[0][u], ans2[0][v]});
    return {anc[0][u], res1, res2};
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N, m = M;
    anc = ans = ans2 = vector<vector<ll> >(LOG, vector<ll>(n + 1));
    adj = vector<vector<array<ll, 3> > >(n + 1);
    dep = cost = cost2 = vector<ll>(n + 1, 0);
    dist = vector<ll>(n + 1, LLONG_MAX);
    for (ll i = 0; i < m; i++) {
        U[i]++, V[i]++;
        adj[U[i]].push_back({V[i], W[i], i});
        adj[V[i]].push_back({U[i], W[i], i});
        w.push_back(W[i]);
    }
    function<void(ll, ll)> dfs = [&](ll u, ll p) {
        if (adj[u].size() > 2) {
            sort(all(adj[u]), [](auto a, auto b) {
                return a[1] < b[1];
            });
            cost2[u] = adj[u][2][1];
        } else cost2[u] = -1;
        anc[0][u] = p;
        ans[0][u] = max(cost[u], cost[p]);
        ans2[0][u] = max(cost2[u], cost2[p]);
        //        cout << u << ' ' << ans2[0][u] << ' ' << p << nl;
        for (ll pw = 1; pw < LOG; pw++) {
            anc[pw][u] = anc[pw - 1][anc[pw - 1][u]];
            ans[pw][u] = max(ans[pw - 1][anc[pw - 1][u]], ans[pw - 1][u]);
            ans2[pw][u] = max(ans2[pw - 1][anc[pw - 1][u]], ans2[pw - 1][u]);
        }
        for (auto [v, we, idx]: adj[u])
            if (v != p)
                cost[v] = we, dep[v] = dep[u] + 1, dfs(v, u);
    };
    dfs(1, 1);
    priority_queue<array<ll, 2>, vector<array<ll, 2> >, greater<> > pq;
    for (ll i = 1; i <= n; i++) {
        if (cost2[i] != -1)
            pq.push({dist[i] = cost2[i], i});
    }
    while (!pq.empty()) {
        auto [c, u] = pq.top();
        pq.pop();
        if (c > dist[u])continue;
//        cout << u << ' ' << dist[u] << nl;
        for (auto [v, we, idx]: adj[u])
            if (max(we, c) < dist[v])
                pq.push({dist[v] = max(we, c), v});
    }

    sort(all(w));
    w.erase(unique(all(w)), w.end());
}

int getMinimumFuelCapacity(int x, int y) {
    x++, y++;
    auto [lc, res1, res2] = lca(x, y);
    if (dist[x] == LLONG_MAX)return -1;
    return max(res1, dist[x]);
}

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