oj.uz

Submission #741418

# Submission time Handle Problem Language Result Execution time Memory
741418 2023-05-14T04:45:48 Z phoebe Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 17072 KB 
#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});
        }
    }
    int bruh = Y;
    while (p[bruh] != -LLINF){
        p[bruh] *= -1; bruh = p[bruh];
    }
    p[X] = X; 
    // FOR(i, n) cout << p[i] << ' '; cout << endl;
    if (dist[Y] >= LLINF) return -1;
    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) break;
        for (auto x : adj[v]){
            ll u = x.F, w = x.S;
            if (p[u] < 0){
                // 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 max(mn, dist[Y]);
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Execution timed out 2073 ms 17072 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -