oj.uz

Submission #873836

# Submission time Handle Problem Language Result Execution time Memory
873836 2023-11-15T21:48:59 Z tvladm2009 Pipes (CEOI15_pipes) C++17
90 / 100
 836 ms 21984 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;
    }
};

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

    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> adj(n + 1);
    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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 1656 KB Output is correct
2 Correct 129 ms 1128 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 3420 KB Output is correct
2 Correct 166 ms 3156 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 9548 KB Output is correct
2 Correct 249 ms 6212 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 11068 KB Output is correct
2 Correct 408 ms 8200 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 13684 KB Output is correct
2 Correct 475 ms 8592 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 13552 KB Output is correct
2 Correct 611 ms 8592 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 12812 KB Output is correct
2 Runtime error 836 ms 21984 KB Memory limit exceeded
3 Halted 0 ms 0 KB -