Submission #1201204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201204		Error42	Pipes (CEOI15_pipes)	C++20	0 / 100	5095 ms	1600 KiB

pipes

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

using namespace std;

int const MAX_N = 1e5;

// 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]);
    }
}

// -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 v;

        v = p;
    }
}

void reroot(int v) {
    while (parent[v] != -1) {
        int const p = parent[v];

        sz[p] -= sz[v];

        swap(parent[v], parent[p]);

        sz[v] += sz[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);

        parent[v] = u;

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

        while (cu != cv) {
#ifdef _DEBUG
            assert(cu != -1 && cv != -1);
#endif

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

            int& pc = up(c);
            dsu::parent[dsu::find(c)] = pc;
            c = 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);
    }

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

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