Submission #397885

#	Time	Username	Problem	Language	Result	Execution time	Memory
397885		yuto1115	Swapping Cities (APIO20_swap)	C++17	100 / 100	1186 ms	59948 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int inf = 1001001001;

class unionfind {
    int n;
public:
    vi par, rank;
    
    unionfind(int n) : n(n), par(n, -1), rank(n, 0) {}
    
    int root(int x) {
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        if (rank[x] == rank[y]) rank[x]++;
        par[x] += par[y];
        par[y] = x;
        return true;
    }
};

namespace {
    struct node {
        int mx;
        bool is_path;
        int x, y;
        
        node(int mx, bool is_path = false, int x = 0, int y = 0)
            : mx(mx), is_path(is_path), x(x), y(y) {}
    };
    
    vector<node> nodes;
    vvi G;
    int sz;
    vvi par;
    vi dep;
    
    int lca(int u, int v) {
        if (dep[u] > dep[v]) swap(u, v);
        if (dep[u] < dep[v]) {
            int dis = dep[v] - dep[u];
            rep(k, 30) if (dis >> k & 1) v = par[k][v];
        }
        assert(dep[u] == dep[v]);
        if (u == v) return u;
        for (int k = 29; k >= 0; k--) {
            if (par[k][u] == par[k][v]) continue;
            u = par[k][u];
            v = par[k][v];
        }
        assert(u != v and par[0][u] == par[0][v]);
        return par[0][u];
    }
}

void dfs(int u, int p, int d) {
    par[0][u] = p;
    dep[u] = d;
    for (int v : G[u]) {
        if (v == p) continue;
        dfs(v, u, d + 1);
    }
}

void init(int n, int m, vi u, vi v, vi w) {
    vi ord(m);
    iota(all(ord), 0);
    sort(all(ord), [&](int i, int j) { return w[i] < w[j]; });
    unionfind uf(n);
    map<int, int> mp;
    rep(i, n) {
        nodes.eb(0, true, i, i);
        mp[i] = i;
    }
    G.resize(n + m + 10);
    for (int i : ord) {
        int a = u[i], b = v[i];
        if (uf.same(a, b)) {
            int r = uf.root(a);
            int now = mp[r];
            if (!nodes[now].is_path) continue;
            int nx = nodes.size();
            G[now].pb(nx);
            G[nx].pb(now);
            nodes.eb(w[i]);
            mp[r] = nx;
        } else {
            int ra = uf.root(a), rb = uf.root(b);
            if (uf.rank[ra] < uf.rank[rb]) {
                swap(a, b);
                swap(ra, rb);
            }
            uf.merge(ra, rb);
            int na = mp[ra], nb = mp[rb];
            int nx = nodes.size();
            G[na].pb(nx);
            G[nb].pb(nx);
            G[nx].pb(na);
            G[nx].pb(nb);
            if (!nodes[na].is_path or !nodes[nb].is_path) {
                nodes.eb(w[i]);
            } else {
                int nx_x = -1, nx_y = -1;
                if (nodes[na].x == a) nx_x = nodes[na].y;
                else if (nodes[na].y == a) nx_x = nodes[na].x;
                if (nodes[nb].x == b) nx_y = nodes[nb].y;
                else if (nodes[nb].y == b) nx_y = nodes[nb].x;
                if (nx_x == -1 or nx_y == -1) {
                    nodes.eb(w[i]);
                } else {
                    nodes.eb(w[i], true, nx_x, nx_y);
                }
            }
            mp.erase(rb);
            mp[ra] = nx;
        }
    }
    assert(mp.size() == 1);
    sz = nodes.size();
    par.resize(30);
    rep(k, 30) par[k].resize(sz);
    dep.resize(sz);
    dfs(sz - 1, -1, 0);
    rep(k, 29) rep(i, sz) {
            if (par[k][i] < 0) par[k + 1][i] = -1;
            else par[k + 1][i] = par[k][par[k][i]];
        }
}

int getMinimumFuelCapacity(int x, int y) {
    int l = lca(x, y);
    if (!nodes[l].is_path) return nodes[l].mx;
    if (nodes[sz - 1].is_path) return -1;
    for (int k = 29; k >= 0; k--) {
        if (par[k][l] < 0) continue;
        if (!nodes[par[k][l]].is_path) continue;
        l = par[k][l];
    }
    assert(nodes[l].is_path);
    l = par[0][l];
    assert(!nodes[l].is_path);
    return nodes[l].mx;
}

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