Submission #1212841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212841		Hamed_Ghaffari	Swapping Cities (APIO20_swap)	C++20	100 / 100	212 ms	52288 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

#define maxs(a, b) (a = max(a, b))

const int MXN = 3e5+5, LOG = 19;

int n, h[MXN], par[MXN][LOG], dsu[MXN], sz[MXN], name[MXN], w[MXN], mx[MXN], d[MXN], timer;
bool cyc[MXN];
vector<int> g[MXN];

int find(int v) {
    return v==dsu[v] ? v : dsu[v] = find(dsu[v]);
}

inline void add(int u, int v, int w) {
    int uu = find(u), vv = find(v);
    if(uu==vv) {
        par[name[uu]][0] = timer;
        g[timer].push_back(name[uu]);
        mx[timer] = max({mx[name[uu]], ++d[u], ++d[v]});
        ::w[timer] = w;
        cyc[timer] = 1;
        name[uu] = timer++;
        return;
    }
    if(sz[uu]<sz[vv]) swap(uu, vv);
    par[name[uu]][0] = par[name[vv]][0] = timer;
    g[timer].push_back(name[uu]); g[timer].push_back(name[vv]);
    mx[timer] = max({mx[name[uu]], mx[name[vv]], ++d[u], ++d[v]});
    cyc[timer] = cyc[name[uu]]|cyc[name[vv]];
    ::w[timer] = w;
    sz[dsu[vv] = uu] += sz[vv];
    name[uu] = timer++;
}

void dfs(int v) {
    for(int i=1; i<LOG; i++)
        par[v][i] = par[par[v][i-1]][i-1];
    for(int u : g[v]) {
        h[u] = h[v]+1;
        dfs(u);
    }
}

inline int jump(int v, int d) {
    for(int i=0; i<LOG; i++)
        if(d>>i&1)
            v = par[v][i];
    return v;
}

inline int LCA(int u, int v) {
    if(h[u]<h[v]) swap(u, v);
    u = jump(u, h[u]-h[v]);
    if(u==v) return u;
    for(int i=LOG-1; i>=0; i--)
        if(par[u][i]!=par[v][i])
            u = par[u][i], v = par[v][i];
    return par[u][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    for(int i=0; i<N; i++) {
        dsu[i] = i;
        sz[i] = 1;
        name[i] = i;
    }
    timer = N;
    vector<int> ord(M);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return W[i] < W[j];
    });
    for(int i=0; i<M; i++) add(U[ord[i]], V[ord[i]], W[ord[i]]);
    par[timer-1][0] = timer-1;
    dfs(timer-1);
}

int getMinimumFuelCapacity(int X, int Y) {
    if(mx[timer-1]<=2 && !cyc[timer-1]) return -1;
    int v = LCA(X, Y);
    if(mx[v]>=3) return w[v];
    for(int i=LOG-1; i>=0; i--)
        if(mx[par[v][i]]<=2 && !cyc[par[v][i]])
            v = par[v][i];
    return w[par[v][0]];
}

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