oj.uz

Submission #428536

# Submission time Handle Problem Language Result Execution time Memory
428536 2021-06-15T12:40:48 Z snasibov05 Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 524292 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 165 ms 1540 KB Output is correct
5 Correct 750 ms 8524 KB Output is correct
6 Correct 804 ms 6372 KB Output is correct
7 Correct 1055 ms 9080 KB Output is correct
8 Correct 1044 ms 7112 KB Output is correct
9 Runtime error 258 ms 524292 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Runtime error 307 ms 524292 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 165 ms 1540 KB Output is correct
5 Correct 750 ms 8524 KB Output is correct
6 Correct 804 ms 6372 KB Output is correct
7 Correct 1055 ms 9080 KB Output is correct
8 Correct 1044 ms 7112 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1950 ms 10700 KB Output is correct
11 Execution timed out 2050 ms 9100 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 165 ms 1540 KB Output is correct
6 Correct 750 ms 8524 KB Output is correct
7 Correct 804 ms 6372 KB Output is correct
8 Correct 1055 ms 9080 KB Output is correct
9 Correct 1044 ms 7112 KB Output is correct
10 Runtime error 258 ms 524292 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 165 ms 1540 KB Output is correct
5 Correct 750 ms 8524 KB Output is correct
6 Correct 804 ms 6372 KB Output is correct
7 Correct 1055 ms 9080 KB Output is correct
8 Correct 1044 ms 7112 KB Output is correct
9 Runtime error 258 ms 524292 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 165 ms 1540 KB Output is correct
6 Correct 750 ms 8524 KB Output is correct
7 Correct 804 ms 6372 KB Output is correct
8 Correct 1055 ms 9080 KB Output is correct
9 Correct 1044 ms 7112 KB Output is correct
10 Runtime error 258 ms 524292 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -