제출 #741423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
741423		phoebe	자매 도시 (APIO20_swap)	C++17	0 / 100	2052 ms	17552 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define F first
#define S second
#define PB push_back
#define FOR(i, n) for (int i = 0; i < n; i++)

const int maxn = 1e5 + 10;
const ll LLINF = 1ll<<50;
ll n, m, dist[maxn], p[maxn], rev_dist[maxn], rev_p[maxn];
vector<pii> adj[maxn];

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
    n = N, m = M;
    FOR(i, m){
        adj[U[i]].PB({V[i], W[i]});
        adj[V[i]].PB({U[i], W[i]});
    }
}

int getMinimumFuelCapacity(int X, int Y){
    fill(dist, dist + n, LLINF); 
    fill(rev_dist, rev_dist + n, LLINF);
    fill(p, p + n, -LLINF); 
    fill(rev_p, rev_p + n, -LLINF);
    priority_queue<pii> pq; pq.push({0, X});
    dist[X] = 0;
    while (!pq.empty()){
        ll v = pq.top().S, d = -pq.top().F; pq.pop();
        if (dist[v] < d) continue;
        for (auto x : adj[v]){
            ll u = x.F, w = x.S;
            if (dist[u] <= max(d, w)) continue;
            dist[u] = max(d, w), p[u] = v;
            pq.push({-dist[u], u});
        }
    }
    if (dist[Y] >= LLINF) return -1;
    bool on_shortest_path[maxn] = {0};
    int bruh = Y;
    while (p[bruh] != -LLINF){
        on_shortest_path[bruh] = true;
        bruh = p[bruh];
    }
    on_shortest_path[X] = true;
    // FOR(i, n) cout << p[i] << ' '; cout << endl;
    ll mn = LLINF;
    pq = priority_queue<pii>();
    pq.push({0, Y}); rev_dist[Y] = 0;
    while (!pq.empty()){
        ll v = pq.top().S, d = -pq.top().F; pq.pop();
        if (rev_dist[v] < d) continue;
        if (v == X) continue;
        for (auto x : adj[v]){
            ll u = x.F, w = x.S;
            if (!on_shortest_path[u]){
                // cout << u << ' ' << v << ' ' << endl;
                mn = min(mn, max({dist[u], d, w}));
            }
            if (rev_dist[u] <= max(d, w)) continue;
            rev_dist[u] = max(d, w), rev_p[u] = v;
            pq.push({-rev_dist[u], u});
        }
    }
    // FOR(i, n) cout << dist[i] << ' '; cout << endl;
    // FOR(i, n) cout << rev_dist[i] << ' '; cout << endl;
    if (mn >= LLINF) return -1;
    // cout << dist[Y] << ' ' << mn << endl;
    return mn;
}

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