Submission #576514

#	Time	Username	Problem	Language	Result	Execution time	Memory
576514		ParsaEs	Swapping Cities (APIO20_swap)	C++14	100 / 100	318 ms	31660 KiB

swap

//InTheNameOfGOD
//PRS;)
#include<bits/stdc++.h>
#include "swap.h"
#define rep(i, l, r) for(ll i = l; i < r; i++)
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
#define pb push_back
#define X first
#define Y second
typedef int ll;
using namespace std;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pi;
constexpr ll inf = 2e9, xm = 2e5 + 5, xn = 1e5 + 5;
vector<pl> p[xn];
vector<ll> g[xn];
pi e[xm];
ll ans[xn], d[xn], n, m;
void init(ll N, ll M, vector<ll> U, vector<ll> V, vector<ll> W)
{
    n = N, m = M;
    rep(i, 0, N) p[i].pb({0, i}), g[i].pb(i), ans[i] = inf;
    rep(i, 0, M) e[i] = {W[i], {U[i], V[i]}};
    sort(e, e + M);
    rep(i, 0, M)
    {
        ll v = e[i].X, x = e[i].Y.X, y = e[i].Y.Y;
        ll x1 = p[x].back().Y, y1 = p[y].back().Y;
        if(x1 == y1)
        {
            ans[x1] = min(ans[x1], v);
            continue;
        }
        if(g[x1].size() < g[y1].size()) swap(x1, y1), swap(x, y);
        ans[x1] = min(ans[x1], max(ans[y1], v)), d[x]++, d[y]++;
        if(d[x] > 2 || d[y] > 2) ans[x1] = min(ans[x1], v);
        for(ll u : g[y1]) p[u].pb({v, x1}), g[x1].pb(u);
    }
}
ll getMinimumFuelCapacity(ll x, ll y)
{
    ll i = p[x].size(), j = p[y].size(), ret = inf;
    i--, j--;
    while(i >= 0 && j >= 0 &&p[x][i].Y == p[y][j].Y)
        ret = min(ret, max(ans[p[x][i].Y], max(p[x][i].X, p[y][j].X))), i--, j--;
    return (ret >= inf ? -1 : ret);
}

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