Submission #1200845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200845		Braabebo10	Swapping Cities (APIO20_swap)	C++20	0 / 100	2094 ms	20820 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;
ll n, m;

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N, m = M;
    adj = vector<vector<array<ll, 3> > >(n + 1);
    for (ll i = 0; i < m; i++) {
        adj[U[i]].push_back({V[i], W[i], i});
        adj[V[i]].push_back({U[i], W[i], i});
    }
}

int getMinimumFuelCapacity(int x, int y) {
    vector<ll> used1(m, 0), dist(n + 1, LLONG_MAX), used2(n + 1, 0);
    vector<array<ll, 2> > par(n + 1, {-1, -1});
    auto dijk = [&](ll s, ll e) {
        dist = vector<ll>(n + 1, LLONG_MAX);
        par = vector<array<ll, 2> >(n + 1, {-1, -1});
        priority_queue<array<ll, 2>, vector<array<ll, 2> >, greater<> > pq;
        pq.push({dist[s] = 0, s});
        par[s] = {s, -1};
        while (!pq.empty()) {
            auto [c, u] = pq.top();
            pq.pop();
            if (c > dist[u])continue;
            for (auto [v, w, idx]: adj[u]) {
                if (used1[idx] or used2[v])continue;
                if (max(c, w) < dist[v])
                    par[v] = {u, idx}, pq.push({dist[v] = max(c, w), v});
            }
        }
        if (dist[e] == LLONG_MAX)return dist[e];
        ll ed = e;
        while (ed != s) {
            used1[par[ed][1]] = 1;
            used2[par[ed][0]] = used2[ed] = 1;
            ed = par[ed][0];
        }
        return dist[e];
    };
    auto clr = [&]() {
        used1 = vector<ll>(m, 0);
        used2 = vector<ll>(n + 1, 0);
    };
    ll res = LLONG_MAX;
    for (ll i: {0, 1}) {
        clr();
        ll cur = dijk(x, y), mni = LLONG_MAX;
        used1[y] = 1;
        dijk(x, y);
        auto dx = dist;
        clr();
        used2[x] = 1;
        dijk(y, x);
        auto dy = dist;
        for (ll u = 1; u <= n; u++) {
            if (u == x or u == y or dy[u] == LLONG_MAX or dx[u] == LLONG_MAX)continue;
//            cout << x << ' ' << y << ' ' << u << ' ' << dy[u] << nl;
            mni = min(mni, max(dx[u], dy[u]));
        }
        cur = max(cur, mni);
        res = min(res, cur);
        swap(x, y);
    }
    return (res == LLONG_MAX ? -1 : res);
}

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