Submission #1043813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043813		VMaksimoski008	Swapping Cities (APIO20_swap)	C++17	7 / 100	242 ms	53288 KiB

swap

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

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

int par[maxn+5], cycle[maxn+5], deg[maxn+5], P[maxn+5], pref[maxn+5], good[maxn+5], d[maxn+5], n, m, N, up[maxn+5][LOG];
vector<int> graph[maxn+5];
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) cycle[n] = 1;
    par[n] = par[a] = par[b] = n;
    if(good[a] || good[b]) good[n] = 1;
    if(cycle[a] || cycle[b]) cycle[n] = 1;
    graph[n].push_back(a);
    if(a != b) graph[n].push_back(b);
}

void dfs(int u) {
    for(int i=1; i<LOG; i++) up[u][i] = up[up[u][i-1]][i-1];

    for(int &v : graph[u]) {
        d[v] = d[u] + 1;
        up[v][0] = u;
        P[v] = u;
        pref[v] = pref[u] + (good[v] || cycle[v]);
        dfs(v);
    }
}

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;
        cycle[i] = deg[i] = good[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) good[n+1] = 1;
        if(deg[v] >= 3) good[n+1] = 1;
        uni(u, v);
    }

    dfs(n);
}

int getMinimumFuelCapacity(int X, int Y) {
    X++; Y++;
    int lca = get_lca(X, Y);
    if(good[lca] || cycle[lca]) return edges[lca-N-1][0];

    int l=0, r=d[lca], ans=-1;
    while(l <= r) {
        int mid = (l + r) / 2, curr = lca;
        for(int j=LOG-1; j>=0; j--) if(mid & (1 << j)) curr = up[curr][j];
        if(pref[lca] - pref[P[curr]]) ans = curr, r = mid - 1;
        else l = mid + 1;
    }

    return (ans == -1 ? -1 : edges[ans-N-1][0]);
}

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