oj.uz

Submission #527240

# Submission time Handle Problem Language Result Execution time Memory
527240 2022-02-17T04:08:16 Z joelau Pipes (CEOI15_pipes) C++14
20 / 100
 5000 ms 50188 KB 
#include <bits/stdc++.h>
using namespace std;

int N,M, ufds[100005], rnk[100005], ufds1[100005], rnk1[100005];
pair<int,int> edges[6000005];

int findSet(int i) {
    return ufds[i] == i ? i : ufds[i] = findSet(ufds[i]);
}

void unionSet (int i, int j) {
    int a = findSet(i), b = findSet(j);
    if (a == b) return;
    if (rnk[a] < rnk[b]) ufds[a] = b;
    if (rnk[a] > rnk[b]) ufds[b] = a;
    if (rnk[a] == rnk[b]) ufds[a] = b, rnk[b]++;
}

int findSet1(int i) {
    return ufds1[i] == i ? i : ufds1[i] = findSet1(ufds1[i]);
}

void unionSet1 (int i, int j) {
    int a = findSet1(i), b = findSet1(j);
    if (a == b) return;
    if (rnk1[a] < rnk1[b]) ufds1[a] = b;
    if (rnk1[a] > rnk1[b]) ufds1[b] = a;
    if (rnk1[a] == rnk1[b]) ufds1[a] = b, rnk1[b]++;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M;
    for (int i = 0; i < N; ++i) ufds[i] = i, rnk[i] = 1;
    for (int i = 0; i < M; ++i) {
        int u,v; cin >> u >> v; u--, v--;
        edges[i] = make_pair(u,v);
        unionSet(u,v);
    }
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) ufds1[j] = j, rnk1[j] = 1;
        for (int j = 0; j < M; ++j) if (j != i) unionSet1(edges[j].first,edges[j].second);
        bool bridge = false;
        for (int i = 0; i < N; ++i) if (findSet1(i) != findSet1(findSet(i)) || findSet(i) != findSet(findSet1(i))) bridge = true;
        if (bridge) cout << edges[i].first+1 << ' ' << edges[i].second+1 << '\n';
    }

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1662 ms 580 KB Output is correct
2 Correct 1993 ms 588 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5034 ms 8456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5037 ms 14448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5103 ms 21492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5072 ms 16340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5072 ms 25268 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5077 ms 33356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5018 ms 42928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5084 ms 50188 KB Time limit exceeded
2 Halted 0 ms 0 KB -