Submission #1199078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199078		browntoad	Swapping Cities (APIO20_swap)	C++20	100 / 100	791 ms	59860 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

namespace{
    const ll maxn = 1e5+5;
    const ll mxpw = 18;
    const int inf = (1<<30);
    int par[maxn][mxpw];
    int bei[maxn][3][mxpw]; // node, edge, tree edge weight
    vector<pii> g[maxn];
    vector<pii> tre[maxn];
    set<int> krem[maxn]; // remaining nodes in dsu that are still deg(u) <= 3
    vector<int> dep(maxn);
    vector<int> dg(maxn);

    int kpar[maxn], jpar[maxn];
}

int kfin(int a){
    if (kpar[a] == a) return a;
    return kpar[a] = kfin(kpar[a]);
}
bool kmerg(int a, int b, int w){
    int ia = a, ib = b;
    a = kfin(a); b = kfin(b);
    if (a == b) return 0;
    tre[ia].pb({ib, w});
    tre[ib].pb({ia, w});

    if (SZ(krem[a]) == 0 || SZ(krem[b]) == 0){ // once a node becomes node 3, all things have to go
        kpar[a] = b;
        for (auto p:krem[a]) bei[p][0][0] = w;
        krem[a].clear();
        for (auto p:krem[b]) bei[p][0][0] = w;
        krem[b].clear();

        return 1;
    }
    if (SZ(krem[a]) > SZ(krem[b])) swap(a, b);
    // merge smaller -> bigger
    kpar[a] = b;
    for (auto p:krem[a]) krem[b].insert(p);
    krem[a].clear();

    return 1;
}
int jfin(int a){
    if (jpar[a] == a) return a;
    return jpar[a] = jfin(jpar[a]);
}
void jmerg(int a, int b){
    a = jfin(a); b = jfin(b);
    if (a == b) return;
    if (dep[a] > dep[b]) jpar[a] = b;
    else jpar[b] = a;
}

void dfs(int u, int pre){
    par[u][0] = pre;
    if (pre == -1) par[u][0] = u;
    REP1(i, mxpw-1){
        par[u][i] = par[par[u][i-1]][i-1];
    } 

    for (auto [v, w]:tre[u]){
        if (v == pre) continue;
        bei[v][2][0] = w;
        dep[v] = dep[u]+1;
        dfs(v, u);
    }
}
void dfs2(int u, int pre){
    // bei all initialized
    REP1(bb, mxpw-1){
        bei[u][0][bb] = min(bei[u][0][bb-1], bei[par[u][bb-1]][0][bb-1]);
        bei[u][1][bb] = min(bei[u][1][bb-1], bei[par[u][bb-1]][1][bb-1]);
        bei[u][2][bb] = max(bei[u][2][bb-1], bei[par[u][bb-1]][2][bb-1]);
    }
    for (auto [v, w]:tre[u]){
        if (v == pre) continue;
        dfs2(v, u);
    }
}

int lca(int a, int b){
    if (dep[a] < dep[b]) swap(a, b);
    int gol = dep[a] - dep[b];
    REP(i, mxpw) if ((gol>>i)&1) a = par[a][i];
    if (a == b) return a;

    RREP(i, mxpw){
        if (par[a][i] != par[b][i]){
            a = par[a][i];
            b = par[b][i];
        }
    }
    return par[a][0];
}
void init(int n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    REP(i, n) REP(j, 2) bei[i][j][0] = inf;
    REP(i, n) kpar[i] = jpar[i] = i;
    REP(i, n) krem[i].insert(i);

    vector<pii> ee;
    REP(i, m){
        ee.pb({W[i], i});
    }
    sort(ALL(ee));

    vector<int> nontre;
    for (auto [w, id]:ee){
        int ia = U[id], ib = V[id];
        dg[ia]++;
        if (dg[ia] == 3){
            int a = kfin(ia);
            if (bei[a][0][0] == inf){
                bei[a][0][0] = w;
                for (auto p:krem[a]) bei[p][0][0] = bei[a][0][0];
                krem[a].clear();
            }
        }
        dg[ib]++;
        if (dg[ib] == 3){
            int b = kfin(ib);
            if (bei[b][0][0] == inf){
                bei[b][0][0] = w;
                for (auto p:krem[b]) bei[p][0][0] = bei[b][0][0];
                krem[b].clear();
            }
        }

        if (kmerg(U[id], V[id], w)){

        }
        else{
            nontre.pb(id);
        }
    }

    dfs(0, -1);

    for (auto id:nontre){
        int w = W[id];
        int u = jfin(U[id]), v = jfin(V[id]);
        int goldep = dep[lca(u, v)];
        while(dep[u] > goldep){
            bei[u][1][0] = w;
            jmerg(u, par[u][0]);
            u = jfin(u);
        }
        while(dep[v] > goldep){
            bei[v][1][0] = w;
            jmerg(v, par[v][0]);
            v = jfin(v);
        }
    }

    dfs2(0, -1);
}

int getjumps(int a, int b, int wh){
    if (dep[a] < dep[b]) swap(a, b);
    int pp = lca(a, b);
    
    int gol = dep[a] - dep[pp] + (wh == 0);
    int ret = inf;
    if (wh == 2) ret = 0;
    REP(i, mxpw){
        if ((gol>>i)&1){
            if (wh == 2) ret = max(ret, bei[a][2][i]);
            else ret = min(ret, bei[a][wh][i]);
            a = par[a][i];
        }
    }

    gol = dep[b] - dep[pp] + (wh == 0);
    REP(i, mxpw){
        if ((gol>>i)&1){
            if (wh == 2) ret = max(ret, bei[b][2][i]);
            else ret = min(ret, bei[b][wh][i]);
            b = par[b][i];
        }
    }
    return ret;
}

int getMinimumFuelCapacity(int X, int Y) {
    int rt = max(getjumps(X, Y, 2), min(getjumps(X, Y, 0), getjumps(X, Y, 1)));
    if (rt == inf) return -1;
    return rt;
}

/*
5 4
0 1 3
0 2 4
0 3 5
0 4 6
10
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4

5 6
0 1 11
1 2 4
0 3 11
2 4 1
0 2 9
1 4 6
10
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
*/

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