oj.uz

Submission #873831

# Submission time Handle Problem Language Result Execution time Memory
873831 2023-11-15T21:44:33 Z tvladm2009 Pipes (CEOI15_pipes) C++17
40 / 100
 817 ms 65536 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);
    while (m--) {
        int u, v;
        std::cin >> u >> v;
        if (t1.merge(u - 1, v - 1) == true) {
            adj[u].emplace_back(v);
            adj[v].emplace_back(u);
        } else if (t2.merge(u - 1, v - 1) == true) {
            adj[u].emplace_back(v);
            adj[v].emplace_back(u);
        }
    }

    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 0 ms 344 KB Output is correct
2 Correct 0 ms 456 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1372 KB Output is correct
2 Correct 3 ms 860 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 6308 KB Output is correct
2 Correct 71 ms 5904 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 11124 KB Output is correct
2 Correct 138 ms 12624 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 196 ms 19536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 261 ms 30344 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 419 ms 44260 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 547 ms 57324 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 655 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 817 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -