Submission #527240

#	Time	Username	Problem	Language	Result	Execution time	Memory
527240		joelau	Pipes (CEOI15_pipes)	C++14	20 / 100	5103 ms	50188 KiB

pipes

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10