Submission #406433

#	Time	Username	Problem	Language	Result	Execution time	Memory
406433		tengiz05	Swapping Cities (APIO20_swap)	C++17	0 / 100	2008 ms	53668 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
constexpr int N = 3e5 + 5;
int n, m;
int up[N][20], f[N], ans[N], tin[N], tout[N];
std::vector<int> e[N], to[N];
struct desu{
    std::vector<int> p;
    desu(int n){
        p.assign(n, 0);
        iota(p.begin(), p.end(), 0);
    }
    int leader(int u){
        while (p[u] != u) u = p[u] = p[p[u]];
        return u;
    }
    void merge(int u, int v){
        u = leader(u);
        v = leader(v);
        if (u == v) return;
        p[v] = u;
    }
    bool same(int u, int v){
        return leader(u) == leader(v);
    }
}d(N);
int timer = 0;
void dfs(int u, int p){
    tin[u] = timer++;
    up[u][0] = p;
    for (int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1];
    for (auto v : to[u]) {
        dfs(v, u);
    }
    tout[u] = timer;
}
bool is(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int lca(int u, int v){
    if (is(u, v)) return u;
    if (is(v, u)) return v;
    for (int i = 19; i >= 0; i--) {
        if (!is(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}
bool answer;
void init(int n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    ::n = n;
    ::m = m;
    std::vector<std::tuple<int, int, int>> edges;
    for (int i = 0; i < m; i++) {
        edges.emplace_back(W[i], U[i], V[i]);
    }
    sort(edges.begin(), edges.end());
    for (auto [w, u, v] : edges) {
        int nd = n++;
        ans[nd] = w;
        if (d.same(u, v)) {
            f[nd] = true;
            to[nd].push_back(d.leader(u));
            d.merge(nd, u);
        } else {
            to[nd].push_back(d.leader(u));
            to[nd].push_back(d.leader(v));
            d.merge(nd, u);
            d.merge(nd, v);
            f[nd] = f[d.leader(u)] | f[d.leader(v)] | (e[u].size() > 2 || e[v].size() > 2);
        }
        e[u].push_back(v);
        e[v].push_back(u);
    }
    assert(n == ::n + m);
    dfs(n - 1, n - 1);
    if (f[n - 1]) answer = true;
}
int getMinimumFuelCapacity(int X, int Y) {
    if (!answer) return -1;
    int l = lca(X, Y);
    while (!f[l]) l = up[l][0];
    return ans[l];
}

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