Submission #777872

#	Time	Username	Problem	Language	Result	Execution time	Memory
777872		t6twotwo	Swapping Cities (APIO20_swap)	C++17	100 / 100	378 ms	84172 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> ans, dep, p;
vector<vector<int>> par;
constexpr int inf = 2e9;
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
    N = n;
    M = m;
    p.resize(N + M);
    iota(p.begin(), p.end(), 0);
    function<int(int)> find = [&](int x) {
        return x == p[x] ? x : p[x] = find(p[x]);
    };
    vector<int> dif(N + M, -1), three(N + M), deg(N), w(N + M);
    vector<vector<int>> ch(N + M);
    auto unite = [&](int x, int y, int t) {
        x = find(x);
        y = find(y);
        dif[t] = 1;
        for (int z : set<int>{x, y}) {
            three[t] |= three[z];
            dif[t] += dif[z];
            p[z] = t;
            ch[t].push_back(z);
        }
    };
    vector<tuple<int, int, int>> edges(M);
    for (int i = 0; i < M; i++) {
        edges[i] = {W[i], U[i], V[i]};
    }
    sort(edges.begin(), edges.end());
    vector<bool> f(N + M);
    for (int i = 0; i < M; i++) {
        auto [z, x, y] = edges[i];
        if (++deg[x] == 3) {
            three[find(x)] = 1;
        }
        if (++deg[y] == 3) {
            three[find(y)] = 1;
        }
        w[N + i] = z;
        unite(x, y, N + i);
        f[N + i] = three[N + i] == 1 || dif[N + i] >= 0;
    }
    ans.resize(N + M);
    dep.resize(N + M);
    par.resize(N + M, vector<int>(20, -1));
    vector<int> stk{inf};
    auto dfs = [&](auto dfs, int x) -> void {
        for (int i = 0; i < 19 && par[x][i] != -1; i++) {
            par[x][i + 1] = par[par[x][i]][i];
        }
        if (f[x]) {
            stk.push_back(w[x]);
        }
        ans[x] = stk.back();
        for (int y : ch[x]) {
            dep[y] = dep[x] + 1;
            par[y][0] = x;
            dfs(dfs, y);
        }
        if (f[x]) {
            stk.pop_back();
        }
    };
    for (int i = 0; i < N + M; i++) {
        if (find(i) == i) {
            dfs(dfs, i);
        }
    }
}
int getMinimumFuelCapacity(int X, int Y) {
    if (p[X] != p[Y]) {
        return -1;
    }
    if (dep[X] < dep[Y]) {
        swap(X, Y);
    }
    for (int i = 19; i >= 0; i--) {
        if (dep[X] - (1 << i) >= dep[Y]) {
            X = par[X][i];
        }
    }
    for (int i = 19; i >= 0; i--) {
        if (par[X][i] != par[Y][i]) {
            X = par[X][i];
            Y = par[Y][i];
        }
    }
    int Z = par[X][0];
    return ans[Z] == inf ? -1 : ans[Z];
}

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