Submission #428536

#	Time	Username	Problem	Language	Result	Execution time	Memory
428536		snasibov05	Swapping Cities (APIO20_swap)	C++14	0 / 100	2050 ms	524292 KiB

swap

#include "swap.h"
#include <vector>
#include <queue>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define oo 1000000001

vector<vector<pii>> ed;

struct data{
    int u, v;
    int cost;

    bool operator>(data d) const{
        if (cost != d.cost) return cost > d.cost;
        else if (u != d.u) return u > d.u;
        else return v > d.v;
    }
};

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    ed.resize(n);
    for (int i = 0; i < m; ++i) {
        ed[u[i]].pb({v[i], w[i]});
        ed[v[i]].pb({u[i], w[i]});
    }
}

int getMinimumFuelCapacity(int x, int y) {

    int n = ed.size();
    vector<vector<int>> cost(n, vector<int>(n, oo));
    vector<vector<bool>> visited(n, vector<bool>(n));
    cost[x][y] = 0;

    priority_queue<data, vector<data>, greater<data>> pq;
    pq.push({x, y, 0});

    while (!pq.empty()){
        data cur = pq.top();
        pq.pop();

        if (visited[cur.u][cur.v]) continue;
        visited[cur.u][cur.v] = true;
        cost[cur.u][cur.v] = min(cost[cur.u][cur.v], cur.cost);

        for (auto [to, w] : ed[cur.u]){
            if (visited[to][cur.v]) continue;
            if (to == cur.v) continue;
            cost[to][cur.v] = min(cost[to][cur.v], max(cost[cur.u][cur.v], w));
            pq.push({to, cur.v, cost[to][cur.v]});
        }

        for (auto [to, w] : ed[cur.v]){
            if (visited[cur.u][to]) continue;
            if (to == cur.u) continue;
            cost[cur.u][to] = min(cost[cur.u][to], max(cost[cur.u][cur.v], w));
            pq.push({cur.u, to,  cost[cur.u][to]});
        }
    }

    if (cost[y][x] == oo) cost[y][x] = -1;

    return cost[y][x];
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:52:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |         for (auto [to, w] : ed[cur.u]){
      |                   ^
swap.cpp:59:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         for (auto [to, w] : ed[cur.v]){
      |                   ^

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