Submission #1156075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156075		KindaGoodGames	Pipes (CEOI15_pipes)	C++17	0 / 100	26 ms	10584 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;
    }
};
vector<bool> vis;
stack<int> occ;

bool DFS(int v, int p, int t, vector<set<int>>& adj, UnionFind& uf2){
    assert(!vis[v]);
    vis[v] = true;
    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;
    vis.resize(n);

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

    vector<set<int>> adjB(n);

    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)){
            DFS(a,a,b,adjB,uf2);
            int u = occ.top();occ.pop();
            vis[u] = false;
            while(occ.size()){
                int w = occ.top(); occ.pop();
                adjB[u].erase(w);
                adjB[w].erase(u);
                uf2.unite(w,u);
                u = w;
                vis[u] = false;
            }
            vis=vector<bool>(n);
        }
    }

    set<pair<int,int>> edges;
    for(int i = 0; i <n; i++){
        for(auto u : adjB[i]){
            if(edges.count({i,u}) || edges.count({u,i})){
                continue;
            }
            edges.insert({i,u});
        }
    }
    cout << endl;
    for(auto u : edges){
        cout << u.first +1 << " " << u.second +1 << endl;
    }
}

• 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