Submission #1303962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303962		Faggi	Swapping Cities (APIO20_swap)	C++20	0 / 100	2099 ms	105908 KiB

swap

#include <bits/stdc++.h>
#define ll int
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
const int MAXN = 1e3 + 1;
vector<pair<ll, ll>> grafo[MAXN];
bool proc[MAXN][MAXN];
ll dist[MAXN][MAXN];
ll n;
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n = N;
    for (ll i = 0; i < M; i++)
    {
        grafo[U[i]].pb({V[i], W[i]});
        grafo[V[i]].pb({U[i], W[i]});
    }
    for (ll i = 0; i < N; i++)
        grafo[i].pb({i, 0});
}

ll INF = INT_MAX;
vector<ll> v;
ll x, y, a, b, dis;
int getMinimumFuelCapacity(int X, int Y)
{
    priority_queue<vector<ll>> pq;
    for(x=0; x<n; x++)
    for(y=0; y<n; y++)
    dist[x][y]=INF;
    memset(proc,0,sizeof(proc));
    pq.push({0, X, Y});
    dist[X][Y] = 0;
    while (sz(pq))
    {
        v = pq.top();
        pq.pop();
        x = v[1];
        y = v[2];
        if (x == Y && y == X)
        {
            if (dist[Y][X] == INF)
                return -1;
            return dist[Y][X];
        }
        if (proc[x][y])
            continue;
        proc[x][y] = 1;
        for (auto &k : grafo[x])
        {
            for (auto &l : grafo[y])
            {
                a = k.fr;
                b = l.fr;
                if (a == b || a == y && b == x)
                    continue;
                dis = max(dist[x][y], max(k.se, l.se));

                if (dis < dist[a][b])
                {
                    dist[a][b] = dis;
                    pq.push({-dis, a, b});
                }
            }
        }
    }
    if (dist[Y][X] == INF)
        return -1;
    return dist[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