Submission #1246598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246598		Thunnus	Pipes (CEOI15_pipes)	C++20	100 / 100	578 ms	14716 KiB

pipes

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
//#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

struct DSU{
    vi par, size_;
    DSU(int n) : par(n), size_(n, 1) {
        iota(par.begin(), par.end(), 0ll);
    }

    inline int find_set(int a){
        return (par[a] == a ? a : par[a] = find_set(par[a]));
    }

    inline bool unite(int a, int b){
        a = find_set(a), b = find_set(b);
        if(a == b) return false;
        if(size_[a] < size_[b]) swap(a, b);
        par[b] = a;
        size_[a] += size_[b];
        return true;
    }

    inline bool same_set(int a, int b){
        return find_set(a) == find_set(b);
    }
};

inline void solve(){
    int n, m, a, b;
    cin >> n >> m;
    vvi adj(n);
	DSU cc(n), tcc(n);
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        a--, b--;
        if(cc.unite(a, b) || tcc.unite(a, b)){
            adj[a].emplace_back(b);
            adj[b].emplace_back(a);
        }
    }

    vi tin(n, -1), low(n, -1);
    int timer = 0;
    vector<pii> ans;
    function<void(int, int)> dfs = [&](int v, int p) -> void {
        tin[v] = low[v] = ++timer;
        bool multiple_edges = false;
        for(int &u : adj[v]){
            if(u == p && !multiple_edges){
				multiple_edges = true;
				continue;
			}
            if(tin[u] != -1){
                low[v] = min(low[v], tin[u]);
            }
            else{
                dfs(u, v);
                low[v] = min(low[v], low[u]);
            }
        }
        if(low[v] == tin[v] && p != -1){
			ans.emplace_back(v, p);
		}
        return;
    };
    for(int i = 0; i < n; i++){
        if(tin[i] == -1){
            dfs(i, -1);
        }
    }

    for(int i = 0; i < sz(ans); i++){
        cout << ans[i].fi + 1 << " " << ans[i].se + 1 << "\n";
    }
    return;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10