Submission #1304768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304768		Faggi	Swapping Cities (APIO20_swap)	C++20	100 / 100	499 ms	111900 KiB

swap

#include <bits/stdc++.h>
#define ll long long
#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 = 1e5 + 1;
const int LOG = 20;
const ll INF = LLONG_MAX;
vector<pair<ll, ll>> grafo[MAXN], grafo2[MAXN], grafo3[MAXN];
ll up[MAXN][LOG], miA[MAXN][LOG], disUp[MAXN][LOG], mi2D[MAXN], mi2DU[MAXN], prof[MAXN], up2[MAXN][LOG], disUp2[MAXN][LOG], con[MAXN], dp[MAXN], dpU[MAXN];
void dfs(ll nod, ll pad)
{
    up[nod][0] = pad;
    ll cant = 0;
    for (auto k : grafo[nod])
    {
        cant++;
        if (cant == 3)
        {
            miA[nod][0] = k.fr;
            break;
        }
    }
    for (ll i = 1; i < LOG; i++)
    {
        up[nod][i] = up[up[nod][i - 1]][i - 1];
        miA[nod][i] = min(miA[nod][i - 1], miA[up[nod][i - 1]][i - 1]);
        disUp[nod][i] = max(disUp[nod][i - 1], disUp[up[nod][i - 1]][i - 1]);
    }

    ll act = 0;
    cant = 0;
    for (auto k : grafo[nod])
    {
        if (k.se == pad)
            continue;
        prof[k.se] = prof[nod] + 1;
        cant++;
        act = max(act, k.fr);
        if (cant == 2)
            mi2D[nod] = min(mi2D[nod], act);
        disUp[k.se][0] = k.fr;
        dfs(k.se, nod);
        dp[nod] = min(dp[nod], max(k.fr, dp[k.se]));
        mi2D[nod] = min(mi2D[nod], max(mi2D[k.se], k.fr));
    }
}

void dfs2(ll nod, ll pad, ll pMiD2)
{
    mi2DU[nod] = pMiD2;
    for (auto k : grafo[nod])
    {
        if (k.se == pad)
            continue;
        ll cant = 0, act = 0, m2D = INF;
        for (auto l : grafo[nod])
        {
            if (l.se == k.se)
                continue;
            cant++;
            act = max(act, l.fr);
            if (cant == 2)
            {
                m2D = act;
                break;
            }
        }
        for (auto l : grafo2[nod])
        {
            if (l.se == k.se || l.se == pad)
                continue;
            m2D = min(m2D, l.fr);
            break;
        }
        dpU[k.se] = min(dpU[k.se], max(min(dp[nod], dpU[nod]), k.fr));
        dfs2(k.se, nod, max(k.fr, min(m2D, mi2DU[nod])));
    }
}
ll aCon = 1;
void dfs3(ll nod, ll pad)
{
    con[nod] = aCon;
    up2[nod][0] = pad;
    for (ll i = 1; i < LOG; i++)
    {
        up2[nod][i] = up2[up2[nod][i - 1]][i - 1];
        disUp[nod][i] = max(disUp[nod][i - 1], disUp[up[nod][i - 1]][i - 1]);
    }
    for (auto k : grafo3[nod])
    {
        if (k.se == pad)
            continue;
        disUp[k.se][0] = k.fr;
        dfs3(k.se, nod);
    }
}

ll id[MAXN];
vector<ll> comp[MAXN];

bool unionfind(ll a, ll b)
{
    ll x = id[a], y = id[b];
    if (x == y)
        return 1;
    if (sz(comp[x]) < sz(comp[y]))
        swap(x, y);
    for (auto k : comp[y])
    {
        comp[x].pb(k);
        id[k] = x;
    }
    return 0;
}

ll n, m, xZ, yZ;
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    vector<vector<ll>> v, v2;
    ll i, j;
    for (i = 0; i < M; i++)
        v.pb({W[i], U[i], V[i]});
    sort(all(v));
    for (i = 0; i < N; i++)
    {
        dp[i] = dpU[i] = INF;
        id[i] = i;
        comp[i] = {i};
    }
    U.resize(0);
    V.resize(0);
    W.resize(0);
    for (i = 0; i < sz(v); i++)
    {
        grafo3[v[i][1]].pb({v[i][0], v[i][2]});
        grafo3[v[i][2]].pb({v[i][0], v[i][1]});
        if (unionfind(v[i][1], v[i][2]))
        {
            dpU[v[i][1]] = dp[v[i][1]] = min(dp[v[i][1]], 1ll * v[i][0]);
            dpU[v[i][2]] = dp[v[i][2]] = min(dp[v[i][2]], 1ll * v[i][0]);
            continue;
        }
        W.pb(v[i][0]);
        U.pb(v[i][1]);
        V.pb(v[i][2]);
    }
    n = N;
    M = m = sz(V);
    for (i = 0; i < MAXN; i++)
    {
        mi2D[i] = INF;
        mi2DU[i] = INF;
        for (j = 0; j < LOG; j++)
        {
            miA[i][j] = INF;
        }
    }

    for (i = 0; i < M; i++)
    {
        grafo[U[i]].pb({W[i], V[i]});
        grafo[V[i]].pb({W[i], U[i]});
    }
    for (i = 0; i < N; i++)
        sort(all(grafo[i]));
    dfs(0, 0);
    for (i = 0; i < M; i++)
    {
        grafo2[U[i]].pb({max(1ll * W[i], mi2D[V[i]]), V[i]});
        grafo2[V[i]].pb({max(1ll * W[i], mi2D[U[i]]), U[i]});
    }
    for (i = 0; i < N; i++)
        sort(all(grafo2[i]));
    dfs2(0, 0, INF);
}

ll k_ans(ll a, ll d)
{
    ll i;
    for (i = 0; i < LOG; i++)
        if ((1 << i) & d)
            a = up[a][i];
    return a;
}

ll lca(ll a, ll b)
{
    if (prof[b] > prof[a])
        swap(a, b);
    if (a == b)
        return a;
    ll i, d = prof[a] - prof[b];
    xZ = k_ans(a, d - 1);
    yZ = b;
    a = k_ans(a, d);
    if (a == b)
        return a;
    for (i = LOG - 1; i >= 0; i--)
    {
        if (up[a][i] != up[b][i])
        {
            a = up[a][i];
            b = up[b][i];
        }
    }
    xZ = a;
    yZ = b;
    return up[a][0];
}

ll dist(ll a, ll b)
{
    if (a == b)
        return 0;
    ll d = prof[a] - prof[b], i, act = 0;
    for (i = 0; i < LOG; i++)
    {
        if ((1 << i) & d)
        {
            act = max(act, disUp[a][i]);
            a = up[a][i];
        }
    }
    return act;
}

ll getMiA(ll a, ll b)
{
    if (a == b)
        return INF;
    a = up[a][0];
    ll d = prof[a] - prof[b], i, act = INF;
    for (i = 0; i < LOG; i++)
    {
        if ((1 << i) & d)
        {
            act = min(act, miA[a][i]);
            a = up[a][i];
        }
    }
    act = min(act, miA[a][0]);
    return act;
}

ll calDis(ll x, ll y)
{
    swap(up, up2);
    swap(disUp, disUp2);
    ll z = lca(x, y);
    ll ans = max(dist(x, z), dist(y, z));
    swap(up, up2);
    swap(disUp, disUp2);
    return ans;
}

ll dis(ll X, ll Y, ll px, ll py)
{
    priority_queue<pair<ll, ll>> pq;
    vector<ll> dist(n, INF), proc(n, 0);
    dist[X] = 0;
    pq.push({0, X});
    ll a, d;
    while (sz(pq))
    {
        a = pq.top().se;
        pq.pop();
        if (proc[a])
            continue;
        proc[a] = 1;
        for (auto k : grafo3[a])
        {
            if ((a == px && k.se == py) || (a == py && k.se == px))
                continue;
            d = max(k.fr, dist[a]);
            if (d < dist[k.se])
            {
                dist[k.se] = d;
                pq.push({-d, k.se});
            }
        }
    }
    return dist[Y];
}

int getMinimumFuelCapacity(int X, int Y)
{
    if (X == Y)
        return -1;
    ll Z = lca(X, Y), act, ag, iniD = max(dist(X, Z), dist(Y, Z));
    act = iniD;
    ag = min(getMiA(X, Z), getMiA(Y, Z));
    if (ag <= act)
        return act;
    if (X != Z)
        ag = min(ag, mi2D[X]);
    if (Y != Z)
        ag = min(ag, mi2D[Y]);
    if (ag <= act)
        return act;
    if (Y == Z)
        swap(X, Y);
    if (X == Z)
    {
        ll cal = 0, cant = 0;
        for (auto k : grafo[X])
        {
            if (k.se == xZ || k.se == yZ)
                continue;
            cant++;
            cal = max(cal, k.fr);
            if (cant == 2)
                break;
        }
        if (cant == 2)
            ag = min(ag, cal);
        if (ag <= act)
            return act;
        for (auto k : grafo2[X])
        {
            if (k.se == xZ || k.se == yZ || k.se == up[X][0])
                continue;
            ag = min(ag, k.fr);
            break;
        }
        if (ag <= act)
            return act;
        ag = min(ag, mi2DU[X]);
        if (ag <= act)
            return act;
        if (xZ == X)
            swap(xZ, yZ);
    }
    act = max(ag, act);
    ll maAr = -1, px = 0, py = 0, a, b;
    a = X;
    b = Y;
    act = min(act, max(iniD, min(dp[Z], dpU[Z])));
    if (act == INF)
        return -1;
    return act;
}

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