제출 #1273311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273311		thuhienne	자매 도시 (APIO20_swap)	C++20	0 / 100	1 ms	572 KiB

swap

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;
    bool operator<(const Edge &o) const {
        return w < o.w;
    }
};

struct Node {
    int parent, size;
    int deg;      // bậc của node
    int cnt0, cnt1; // số node bậc 1 và bậc 2 trong component nếu là root
    int l, r;
};

struct PersistentDSU {
    int n;
    vector<int> root; // root[version]
    vector<Node> seg;

    PersistentDSU(int n_) : n(n_) {
        seg.reserve(40 * n); // phòng đủ bộ nhớ
        int initRoot = build(1, n);
        root.push_back(initRoot);
    }

    int build(int l, int r) {
        int id = seg.size();
        seg.push_back({});
        if (l == r) {
            seg[id].parent = l;
            seg[id].size = 1;
            seg[id].deg = 0;
            seg[id].cnt0 = 0;
            seg[id].cnt1 = 0;
            return id;
        }
        int mid = (l + r) / 2;
        seg[id].l = build(l, mid);
        seg[id].r = build(mid+1, r);
        return id;
    }

    Node query(int id, int l, int r, int pos) {
        if (l == r) return seg[id];
        int mid = (l + r) / 2;
        if (pos <= mid) return query(seg[id].l, l, mid, pos);
        else return query(seg[id].r, mid+1, r, pos);
    }

    int update(int prev, int l, int r, int pos, Node val) {
        int id = seg.size();
        seg.push_back(seg[prev]); // copy node
        if (l == r) {
            seg[id] = val;
            return id;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) seg[id].l = update(seg[prev].l, l, mid, pos, val);
        else seg[id].r = update(seg[prev].r, mid+1, r, pos, val);
        return id;
    }

    int find(int rootId, int u) {
        Node nu = query(rootId, 1, n, u);
        if (nu.parent == u) return u;
        return find(rootId, nu.parent);
    }

    int unionSet(int rootId, int u, int v) {
        u = find(rootId, u);
        v = find(rootId, v);
        if (u == v) return rootId;
        Node nu = query(rootId, 1, n, u);
        Node nv = query(rootId, 1, n, v);

        if (nu.size < nv.size) swap(u, v), swap(nu, nv);

        // v -> u
        nv.parent = u;
        int newRoot = update(rootId, 1, n, v, nv);
        nu.size += nv.size;
        nu.cnt0 += nv.cnt0;
        nu.cnt1 += nv.cnt1;
        newRoot = update(newRoot, 1, n, u, nu);
        return newRoot;
    }

    int incDeg(int rootId, int u) {
        Node nu = query(rootId, 1, n, u);
        int r = find(rootId, u);
        Node nr = query(rootId, 1, n, r);

        if (nu.deg == 1) nr.cnt0--; // bậc 1 -> 2
        if (nu.deg == 0) nr.cnt0++;
        if (nu.deg == 1) nr.cnt1++;

        nu.deg++;
        rootId = update(rootId, 1, n, u, nu);
        rootId = update(rootId, 1, n, r, nr);
        return rootId;
    }

    // check điều kiện Hamilton path component chứa x,y
    bool check(int rootId, int x, int y) {
        int rx = find(rootId, x);
        int ry = find(rootId, y);
        if (rx != ry) return false;
        Node nr = query(rootId, 1, n, rx);
        return !(nr.cnt1 == nr.size - 2 && nr.cnt0 == 2);
    }
};

int n, m, q;
vector<Edge> edges;
PersistentDSU *dsu;
vector<int> versionRoot;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N; m = M;
    edges.resize(m);
    for (int i = 0; i < m; i++) {
        edges[i] = {U[i]+1, V[i]+1, W[i]}; // shift sang 1-based
    }
    sort(edges.begin(), edges.end());
    dsu = new PersistentDSU(n);
    versionRoot.resize(m+1);
    versionRoot[0] = dsu->root[0];
    for (int i = 1; i <= m; i++) {
        int rootId = versionRoot[i-1];
        rootId = dsu->incDeg(rootId, edges[i-1].u);
        rootId = dsu->incDeg(rootId, edges[i-1].v);
        rootId = dsu->unionSet(rootId, edges[i-1].u, edges[i-1].v);
        versionRoot[i] = rootId;
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    X++, Y++;
    int l = 1, r = m, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (dsu->check(versionRoot[mid], X, Y)) {
            ans = edges[mid-1].w;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

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