Submission #1198131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198131		Blistering_Barnacles	Swapping Cities (APIO20_swap)	C++20	30 / 100	1515 ms	589824 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = (int)2e5 + 5;
vector<pair<int, int>> adj[N];
int mx[18][N], dp[18][N], dep[N], dis[N];
pair<int, int> kth(int v, int k) {
    int ret = 0;
    for (int j = 0; j < 18; j++) {
        if ((1 << j) & k) {
            ret = max(ret, mx[j][v]);
            v = dp[j][v];
        }
    }
    return make_pair(v, ret);
}
pair<int, int> Lca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    int ret = 0;
    tie(v, ret) = kth(v, dep[v] - dep[u]);
    for (int j = 17; j >= 0; j--) {
        if (dp[j][v] != dp[j][u]) {
            ret = max({ret, mx[j][u], mx[j][v]});
            v = dp[j][v], u = dp[j][u];
        }
    }
    if (u == v) return make_pair(u, ret);
    else return make_pair(dp[0][u], max({ret, mx[0][u], mx[0][v]}));
}
void dfs(int v, int par) {
    dep[v] = dep[par] + 1;
    for (auto [u, w]: adj[v]) {
        if (u == par) continue;
        mx[0][u] = w;
        dp[0][u] = v;
        for (int j = 1; j < 18; j++) {
            mx[j][u] = max(mx[j - 1][u], mx[j - 1][dp[j - 1][u]]);
            dp[j][u] = dp[j - 1][dp[j - 1][u]];
        }
        dfs(u, v);
    }
}
void init(int N2, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N2, m = M;
    for (int i = 0; i < m; i++) {
        auto [u, v, w] = make_tuple(U[i] + 1, V[i] + 1, W[i]);
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int i = 1; i <= n; i++) {
        sort(adj[i].begin(), adj[i].end(), [&](pair<int, int> a, pair<int, int> b) {
            return a.second < b.second;
        });
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> se;
    for (int i = 1; i <= n; i++) {
        if ((int)adj[i].size() > 2) {
            dis[i] = adj[i][2].second;
            se.push({dis[i], i});
        } else dis[i] = INT_MAX;
    }
    while (!se.empty()) {
        auto [ds, v] = se.top();
        se.pop();
        if (ds != dis[v]) continue;
        for (auto [u, w]: adj[v]) {
            if (dis[u] > max(dis[v], w)) {
                dis[u] = max(dis[v], w);
                se.push({dis[u], u});
            }
        }
    }
    dfs(1, 0);
}
int getMinimumFuelCapacity(int X, int Y) {
    auto [u, v] = make_tuple(X + 1, Y + 1);
    if (dis[u] == INT_MAX) return -1;
    return max(Lca(u, v).second, min(dis[u], dis[v]));
}

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