Submission #1043822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043822		VMaksimoski008	Swapping Cities (APIO20_swap)	C++17	100 / 100	165 ms	63172 KiB

swap

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

const int maxn = 3e5 + 5;
const int LOG = 20;

int par[maxn], C[maxn], deg[maxn], dp[maxn], P[maxn], ok[maxn], G[maxn], d[maxn], n, m, N, up[maxn][LOG];
vector<int> graph[maxn];
vector<array<int, 3> > edges;

int find(int u) {
    if(u == par[u]) return u;
    return par[u] = find(par[u]);
}

void uni(int a, int b) {
    a = find(a); b = find(b); n++;
    if(a == b) C[n] = 1;
    par[n] = par[a] = par[b] = n;
    if(G[a] || G[b]) G[n] = 1;
    if(C[a] || C[b]) C[n] = 1;
    graph[n].push_back(a);
    if(a != b) graph[n].push_back(b);
}

void dfs(int u, int last) {
    for(int i=1; i<LOG; i++) up[u][i] = up[up[u][i-1]][i-1];
    if(ok[u]) last = u;
    dp[u] = last;

    for(int &v : graph[u]) {
        d[v] = d[u] + 1;
        up[v][0] = u;
        P[v] = u;
        dfs(v, last);
    }
}

int get_lca(int a, int b) {
    if(d[a] < d[b]) swap(a, b);
    int D = d[a] - d[b];
    for(int j=LOG-1; j>=0; j--)
        if(D & (1 << j)) a = up[a][j];

    if(a == b) return a;

    for(int j=LOG-1; j>=0; j--)
        if(up[a][j] != up[b][j]) a = up[a][j], b = up[b][j];
    return up[a][0];
}

void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
    n = _N;
    N = _N;
    m = _M;

    for(int i=1; i<=_N+_M; i++) {
        par[i] = i;
        C[i] = deg[i] = G[i] = 0;
    }

    for(int i=0; i<m; i++) edges.push_back({ W[i], U[i] + 1, V[i] + 1});
    sort(edges.begin(), edges.end());
    for(auto &[w, u, v] : edges) {
        deg[u]++; deg[v]++;
        if(deg[u] >= 3 || deg[v] >= 3) G[n+1] = 1;
        uni(u, v);
    }

    for(int i=1; i<=n; i++) ok[i] = (G[i] || C[i]);
    dfs(n, -1);
}

int getMinimumFuelCapacity(int X, int Y) {
    int L = get_lca(X+1, Y+1);
    if(dp[L] == -1) return -1;
    return edges[dp[L]-N-1][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