Submission #1246953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246953		Turkhuu	Swapping Cities (APIO20_swap)	C++20	100 / 100	272 ms	78472 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
int N, M, lgNM, timer;
vector<int> edge_cnt, node_cnt, l, r, p, w, lvl, deg3;
vector<vector<int>> par, ch;
int find(int x) {return p[x] == x ? x : p[x] = find(p[x]);}
void dfs(int x) {
    (x < N ? node_cnt : edge_cnt)[x]++;
    for (int i = 0; i < lgNM && par[x][i] != -1; i++)
        par[x][i + 1] = par[par[x][i]][i];
    l[x] = timer;
    if (x < N) timer++;
    for (int y : ch[x]) {
        par[y][0] = x;
        lvl[y] = lvl[x] + 1;
        dfs(y);
        deg3[x] |= deg3[y];
        node_cnt[x] += node_cnt[y];
        edge_cnt[x] += edge_cnt[y];
    }
    r[x] = timer;
}
int lca(int x, int y) {
    if (lvl[x] < lvl[y]) swap(x, y);
    FOR(i, 0, lgNM) if ((lvl[x] - lvl[y]) >> i & 1) x = par[x][i];
    if (x == y) return x;
    ROF(i, lgNM, 0) if (par[x][i] != par[y][i]) x = par[x][i], y = par[y][i];
    return par[x][0];
}
void init(int _N, int _M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    N = _N, M = _M; lgNM = __lg(N + M);
    l.resize(N + M);
    r.resize(N + M);
    w.resize(N + M);
    p.resize(N + M); iota(p.begin(), p.end(), 0);
    ch.resize(N + M);
    lvl.resize(N + M);
    deg3.resize(N + M);
    edge_cnt.resize(N + M);
    node_cnt.resize(N + M);
    par.resize(N + M, vector<int>(lgNM + 1, -1));
    vector<int> ord(M), deg(N);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {return W[i] < W[j];});
    FOR(oi, 0, M - 1) {
        int i = ord[oi], x = U[i], y = V[i];
        if (++deg[x] >= 3 || ++deg[y] >= 3) deg3[N + oi] = 1;
        x = find(x), y = find(y);
        ch[N + oi].push_back(x);
        if (x != y) ch[N + oi].push_back(y);
        p[x] = p[y] = N + oi, w[N + oi] = W[i];
    }
    dfs(N + M - 1);
}
bool check(int x) {
    return edge_cnt[x] >= node_cnt[x] || deg3[x];
}
int getMinimumFuelCapacity(int X, int Y) {
    if (!check(N + M - 1)) return -1;
    int Z = lca(X, Y);
    if (check(Z)) return w[Z];
    ROF(i, lgNM, 0) if (par[Z][i] != -1 && !check(par[Z][i])) Z = par[Z][i];
    return w[par[Z][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