Submission #873838

#	Time	Username	Problem	Language	Result	Execution time	Memory
873838		tvladm2009	Pipes (CEOI15_pipes)	C++17	100 / 100	767 ms	11164 KiB

pipes

#include <bits/stdc++.h>

using i64 = long long;
struct DSU {
    std::vector<int> f;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        f[y] = x;
        return true;
    }
};

constexpr int N = 1e5 + 7;

std::vector<int> adj[N];

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

    int n, m;
    std::cin >> n >> m;
    DSU t1(n), t2(n);
    int cnt = 0;
    while (m--) {
        int u, v;
        std::cin >> u >> v;
        if (t1.merge(u - 1, v - 1) == true) {
            adj[u].push_back(v);
            adj[v].push_back(u);
            cnt++;
        } else if (t2.merge(u - 1, v - 1) == true) {
            adj[u].push_back(v);
            adj[v].push_back(u);
            cnt++;
        }
    }
    assert(cnt <= 2 * n);

    std::vector<int> level(n + 1, -1);
    auto dfs = [&](auto self, int u, int par) -> int {
        int low = level[u];
        bool p = false;
        for (auto v : adj[u]) {
            if (level[v] == -1) {
                level[v] = level[u] + 1;
                low = std::min(low, self(self, v, u));
            } else if (v == par && p == false) {
                p = true;
            } else {
                low = std::min(low, level[v]);
            }
        }
        if (par != -1 && low == level[u]) {
            std::cout << par << " " << u << "\n";
        }
        return low;
    };
    for (int i = 1; i <= n; i++) {
        if (level[i] == -1) {
            level[i] = 0;
            dfs(dfs, i, -1);
        }
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 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