Submission #1201685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201685		Error42	Pipes (CEOI15_pipes)	C++20	90 / 100	950 ms	1616 KiB

pipes

#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

int const MAX_N = 1e5;

void dassert(bool const statement) {
#ifdef _DEBUG
    assert(statement);
#endif
}

// 2 * MAX_N * 4 B = 0.8 MB
namespace dsu {
    int parent[MAX_N];

    void init() {
        iota(parent, parent + MAX_N, 0);
    }

    int find(int const x) {
        if (parent[x] == x)
            return x;

        return parent[x] = find(parent[x]);
    }

    // This probably breaks the time-complexity.
    void reroot(int const x) {
        int const r = find(x);

        parent[r] = x;
        parent[x] = x;
    }
}

// -1 if none
int parent[MAX_N];
int sz[MAX_N];

int& up(int const v) {
    return parent[dsu::find(v)];
}

int root(int v) {
    while (true) {
        int const p = up(v);

        if (p == -1)
            return dsu::find(v);

        v = p;
    }
}

void reroot(int v) {
    int const fv = dsu::find(v);
    int const p = parent[fv];

    dassert(v != -1 && fv != -1);
    dassert(v != p && fv != p);

    if (p == -1) {
        sz[v] = sz[fv];
        dsu::reroot(v);
        return;
    }

    reroot(p);

    sz[v] = sz[p];
    sz[p] -= sz[fv];
    
#ifdef _DEBUG
    dassert(sz[v] > sz[p]);
#endif

    parent[fv] = -1;
    dsu::reroot(v);
    parent[p] = fv;

    dassert(parent[v] == -1 && parent[fv] == -1 && parent[p] != p);
}

void add_edge(int u, int v) {
    int ru = root(u);
    int rv = root(v);

    if (ru != rv) {
        if (sz[ru] < sz[rv]) {
            swap(u, v);
            swap(ru, rv);
        }

        reroot(v);

        dassert(u != v);
        parent[v] = u;

        do {
            u = dsu::find(u);
            sz[u] += sz[v];
            u = parent[u];
        } while (u != -1);
    }
    else {
        int cu = dsu::find(u);
        int cv = dsu::find(v);

        while (cu != cv) {
            dassert(cu != -1 && cv != -1);

            int& c = sz[cu] < sz[cv] ? cu : cv;

            int& pc = parent[c];
            dassert(pc != -1 && pc != c);
            dsu::parent[c] = pc;
            c = dsu::find(pc);
            pc = -1;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    dsu::init();
    fill(sz, sz + MAX_N, 1);
    fill(parent, parent + MAX_N, -1);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;

        add_edge(u, v);
    }

#ifdef _DEBUG
    cout << "\n";
#endif

    for (int i = 0; i < n; i++)
        if (parent[i] != -1)
            cout << i + 1 << " " << parent[i] + 1 << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10