Submission #561057

#	Time	Username	Problem	Language	Result	Execution time	Memory
561057		nghiass001	Swapping Cities (APIO20_swap)	C++17	100 / 100	378 ms	39840 KiB

swap

#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
#define getbit(x, i) (((x) >> (i)) & 1)
using namespace std;
const int N = 200005, logN = 19;
int n, depth[N], deg[N], dsu[N], isAny[N], ans[N];
int p[N][logN];
vector<int> S[N];

int DAD(int u) {
    return dsu[u] < 0 ? u : dsu[u] = DAD(dsu[u]);
}

void Union(int u, int v, int w) {
    int pu = DAD(u);
    int pv = DAD(v);
    if (pu == pv) {
        if (!isAny[pu]) {
            isAny[pu] = true;
            ans[pu] = w;
        }
        return;
    }
    int p_uv = n++;

    dsu[pu] = dsu[pv] = p_uv;
    S[p_uv].push_back(pu);
    S[p_uv].push_back(pv);

    isAny[p_uv] = (isAny[pu] || isAny[pv] || deg[u] > 1 || deg[v] > 1);
    if (isAny[p_uv]) ans[p_uv] = w;
    ++deg[u];
    ++deg[v];
}

void DFS(int u, int pa) {
    if (!isAny[u] && isAny[pa]) {
        isAny[u] = true;
        ans[u] = ans[pa];
    }
    depth[u] = depth[pa] + 1;
    p[u][0] = pa;
    REP(i, 1, logN) p[u][i] = p[p[u][i - 1]][i - 1];
    for(int v : S[u]) DFS(v, u);
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    fill(dsu, dsu + n*2, -1);

    vector<int> tmp;
    REP(i, 0, M) tmp.push_back(i);

    sort(tmp.begin(), tmp.end(), [&] (int x, int y) { return W[x] < W[y]; });
    for(int id : tmp) {
        Union(U[id], V[id], W[id]);
    }
    REP(i, 0, logN) p[n][i] = n;
    DFS(n - 1, n);
}

int LCA(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    int diff = depth[v] - depth[u];
    REPD(i, logN, 0) if (getbit(diff, i)) v = p[v][i];
    REPD(i, logN, 0) if (p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
    return u == v ? u : p[u][0];
}

int getMinimumFuelCapacity(int u, int v) {
    int pa = LCA(u, v);
    return isAny[pa] ? ans[pa] : -1;
}

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