Submission #1247533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247533		badge881	Swapping Cities (APIO20_swap)	C++20	100 / 100	291 ms	65388 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll INF = 1e15;

vector<vector<ll>> adj, up;
vector<ll> s, p, v2, dg, v3, v4, dist;
vector<tuple<ll, ll, ll>> edges;

ll cnt = 0, n;

ll _find(ll x)
{
    if (p[x] != x)
        p[x] = _find(p[x]);
    return p[x];
}

void _union(ll a, ll b, ll w)
{
    ll x = a, y = b;
    a = _find(a), b = _find(b);
    if (a == b)
    {
        adj[cnt].push_back(v3[a]);
        adj[v3[a]].push_back(cnt);
        dg[x]++;
        dg[y]++;
        v2[cnt] = 1;
        v4[cnt] = w;
        v3[a] = cnt++;
        return;
    }
    adj[cnt].push_back(v3[a]);
    adj[v3[a]].push_back(cnt);
    adj[cnt].push_back(v3[b]);
    adj[v3[b]].push_back(cnt);
    dg[x]++;
    dg[y]++;
    if (dg[x] >= 3 || dg[y] >= 3)
        v2[cnt] = 1;
    if (v2[v3[a]] || v2[v3[b]])
        v2[cnt] = 1;
    v4[cnt] = w;
    if (s[a] < s[b])
        swap(a, b);
    v3[a] = cnt;
    s[a] += s[b];
    p[b] = a;
    cnt++;
}

void dfs(ll node, ll parent, ll val)
{
    up[node][0] = parent;
    if (v2[node])
        val = v4[node];
    v4[node] = val;

    if (dist[parent] - dist[up[parent][1]] == dist[up[parent][1]] - dist[up[up[parent][1]][1]])
        up[node][1] = up[up[parent][1]][1];
    else
        up[node][1] = parent;

    for (ll to : adj[node])
    {
        if (to == parent)
            continue;
        dist[to] = dist[node] + 1;
        dfs(to, node, val);
    }
}

ll lca(ll a, ll b)
{
    if (dist[a] < dist[b])
        swap(a, b);
    while (dist[a] > dist[b])
    {
        if (dist[up[a][1]] >= dist[b])
            a = up[a][1];
        else
            a = up[a][0];
    }
    if (a == b)
        return v4[a];
    while (up[a][0] != up[b][0])
    {
        if (up[a][1] != up[b][1])
        {
            a = up[a][1];
            b = up[b][1];
        }
        else
        {
            a = up[a][0];
            b = up[b][0];
        }
    }
    return v4[up[a][0]];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
    n = N;
    cnt = N;

    adj.assign(N + M + 10, {});
    up.assign(N + M + 10, vector<ll>(2));
    p.resize(N + 1);
    s.assign(N + 1, 1);
    dg.assign(N + 1, 0);
    v2.assign(N + M + 10, 0);
    v3.resize(N + M + 10);
    v4.resize(N + M + 10);
    dist.assign(N + M + 10, 0);

    iota(p.begin(), p.end(), 0);
    iota(v3.begin(), v3.end(), 0);

    edges.clear();
    for (int i = 0; i < M; i++)
    {
        edges.emplace_back(W[i], V[i], U[i]);
    }

    sort(edges.begin(), edges.end());
    for (auto &[w, y, x] : edges)
        _union(x, y, w);

    up[cnt - 1][0] = up[cnt - 1][1] = cnt - 1;
    dfs(cnt - 1, cnt - 1, -1);
}

int getMinimumFuelCapacity(int X, int Y)
{
    return lca(X, Y);
}

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