oj.uz

Submission #873838

# Submission time Handle Problem Language Result Execution time Memory
873838 2023-11-15T21:51:06 Z tvladm2009 Pipes (CEOI15_pipes) C++17
100 / 100
 767 ms 11164 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3160 KB Output is correct
2 Correct 3 ms 2904 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2904 KB Output is correct
2 Correct 62 ms 2908 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 3408 KB Output is correct
2 Correct 127 ms 3164 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 4688 KB Output is correct
2 Correct 162 ms 4612 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 8732 KB Output is correct
2 Correct 231 ms 6632 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 9556 KB Output is correct
2 Correct 406 ms 7720 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 11164 KB Output is correct
2 Correct 483 ms 8276 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 641 ms 11096 KB Output is correct
2 Correct 609 ms 8536 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 10664 KB Output is correct
2 Correct 763 ms 9084 KB Output is correct