Submission #1156085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156085		KindaGoodGames	Pipes (CEOI15_pipes)	C++17	0 / 100	5094 ms	12284 KiB

pipes

#include<bits/stdc++.h>

using namespace std;

struct UnionFind{
    vector<int> par;

    UnionFind(int n){
        par.resize(n);
        iota(par.begin(),par.end(),0);
    }
    int find(int i){
        if(par[i] == i) return i;
        else return par[i] = find(par[i]);
    }
    void unite(int i, int j){
        i = find(i); j = find(j);
        par[i] = j;
    }
}; 
stack<int> occ;

bool DFS(int v, int p, int t, vector<set<int>>& adj, UnionFind& uf2){ 
    if(uf2.find(v) == uf2.find(t)){
        occ.push(v);
        return true;
    }
    bool onPath = false;
    for(auto u : adj[v]){
        if(u == p) continue;

        bool ans = DFS(u,v,t,adj, uf2);
        onPath |= ans;
    }
    if(onPath){
        occ.push(v);
    }
    return onPath;
}
int main(){
    int n, m;
    cin >> n >> m; 

    UnionFind ufC(n);
    UnionFind uf2(n);

    vector<set<int>> adjB(n);
    set<pair<int,int>> bridges;
    for(int k = 0; k < m; k++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        if(uf2.find(a) == uf2.find(b)){
            continue;
        }else if(uf2.find(a) != uf2.find(b) && ufC.find(a) != ufC.find(b)){
            // add a new bridge 
            adjB[a].insert(b);
            adjB[b].insert(a);
            ufC.unite(a,b);  
        }else if(uf2.find(a) != uf2.find(b) && ufC.find(a) == ufC.find(b)){
            // do a DFS on the bridge tree and return the path of bridges
            // in the 2CC  
            DFS(a,a,b,adjB,uf2);
             
            // erase the path 
            int u = occ.top();occ.pop(); 
            while(occ.size()){
                int w = occ.top(); occ.pop(); 
                uf2.unite(w,u);
                bridges.erase({w,u});
                bridges.erase({u,w});
                u = w; 
            } 
        }
    }

    for(auto p : bridges){
        cout << p.first+1 << p.second+1 << "\n";
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 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