Submission #1304306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304306		Faggi	Swapping Cities (APIO20_swap)	C++20	7 / 100	296 ms	78048 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];
ll up[MAXN][LOG], miA[MAXN][LOG], disUp[MAXN][LOG], mi2D[MAXN], mi2DU[MAXN], prof[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);
        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,mi2D[l.se]);
            break;
        }
        dfs2(k.se,nod,max(k.fr,min(m2D,mi2DU[nod])));
    }
}

ll n, m, xZ, yZ;
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n = N;
    m = M;
    if (M > N - 1)
        return;

    ll i, j;
    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({mi2D[V[i]], V[i]});
        grafo2[V[i]].pb({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;
}

int getMinimumFuelCapacity(int X, int Y)
{
    if (m > n - 1 || X == Y)
        return -1;
    ll Z = lca(X, Y), act = max(dist(X, Z), dist(Y, Z)), ag;
    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;
    }
    act=max(ag,act);
    if(act==INF)
        return -1;
    return act;
}

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