Submission #295683

#	Time	Username	Problem	Language	Result	Execution time	Memory
295683		junseo	Swapping Cities (APIO20_swap)	C++17	100 / 100	490 ms	48740 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(v) v.begin(), v.end()
using namespace std;
typedef pair<int, int> pii;

const int maxn = 1e5 + 10;
const int maxm = 2e5 + 10;
const int maxv = maxn * 3;

struct Node {
    int pa;
    int s, e, w;
    Node(void) : pa(-1), s(-1), e(-1), w(-1) {}
    Node(int pa, int s, int e, int w) : pa(pa), s(s), e(e), w(w) {}
};

int V = 0;
int p[20][maxv], h[maxv];
Node info[maxv];
vector<int> adj[maxv];

int fnd(int x) {
    if(info[x].pa == x) return x;
    return info[x].pa = fnd(info[x].pa);
}

void uni(int a, int b, int w) {
    int x = fnd(a), y = fnd(b);
    if(x == y) {
        if(!~info[x].s) return;
        int z = ++V;
        info[z] = Node(z, -1, -1, w);
        p[0][x] = z;
        info[x].pa = z;
        return;
    }
    int z = ++V;
    p[0][x] = p[0][y] = z;
    info[x].pa = info[y].pa = z;
    info[z] = Node(z, (info[x].s ^ info[x].e ^ a), (info[y].s ^ info[y].e ^ b), w);

    bool af = (a == info[x].s || a == info[x].e), bf = (b == info[y].s || b == info[y].e);
    if(!~info[x].s || !~info[y].s || !af || !bf)    info[z].s = info[z].e = -1;
}

void dfs(int u) {
    for(auto v : adj[u]) {
        h[v] = h[u] + 1;
        dfs(v);
    }
}

void init(int N, int M, vector<int> _u, vector<int> _v, vector<int> _w) {
    V = N;
    for(int i = 1; i <= N; ++i) info[i] = Node(i, i, i, 0);
    vector<pair<int, pii>> E;
    for(int i = 0; i < M; ++i)  E.eb(_w[i], pii(++_u[i], ++_v[i]));
    sort(all(E));
    for(auto [w, t] : E)    uni(t.fi, t.se, w);
    for(int i = 1; i <= V; ++i) if(~info[i].s)  info[i].w = -1;
    for(int i = 1; i < 20; ++i) for(int j = 1; j <= V; ++j) p[i][j] = p[i - 1][p[i - 1][j]];
    for(int i = 1; i < V; ++i)  adj[p[0][i]].eb(i);
    dfs(V);
}

int lca(int u, int v) {
    if(h[u] < h[v]) swap(u, v);
    for(int i = 19; i >= 0; --i) if(h[u] - (1 << i) >= h[v])    u = p[i][u];
    if(u == v)  return u;
    for(int i = 19; i >= 0; --i) if(p[i][u] != p[i][v]) {
        u = p[i][u];
        v = p[i][v];
    }
    return p[0][u];
}

int getMinimumFuelCapacity(int X, int Y) {
    int Z = lca(++X, ++Y);
    if(!~info[Z].s) return info[Z].w;
    for(int i = 19; i >= 0; --i) if(~info[p[i][Z]].s)   Z = p[i][Z];
    return info[p[0][Z]].w;
}

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