Submission #1190488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190488		zh_h	Swapping Cities (APIO20_swap)	C++17	0 / 100	0 ms	324 KiB

swap

#include<bits/stdc++.h>
#define pb push_back
using namespace std;

vector<vector<pair<int, int>>> edge;
vector<vector<int>> cost;
int N;

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

    N = n;
}

int getMinimumFuelCapacity (int x, int y) {
    cost.clear();
    cost.resize(N+1, vector<int>(N+1, 1e9));

    priority_queue<pair<int, pair<int, int>>> q;
    vector<vector<int>> visited(N+1, vector<int>(N+1, false));
    cost[x][y] = 0; visited[x][y] = true;

    q.push({0, {x, y}});

    while (!q.empty()) {
        int w = -q.top().first;
        int a = q.top().second.first, b = q.top().second.second;
        q.pop();

        visited[a][b] = true;
        cost[a][b] = w;

        for (auto i : edge[a]) {
            if (i.first == b) continue;
            if (visited[i.first][b]) continue;

            int new_w = max(w, i.second);
            q.push({-new_w, {i.first, b}});
        }

        for (auto i : edge[b]) {
            if (i.first == a) continue;
            if (visited[a][i.first]) continue;

            int new_w = max(w, i.second);
            q.push({-new_w, {a, i.first}});
        }
    }

    return cost[y][x];;
}

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