제출 #1326375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326375		pouya88	Pipes (CEOI15_pipes)	C++20	100 / 100	662 ms	14704 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
//#define int int64_t
#define endl '\n'
#define ld long double
#define prior priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> 
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define kill(x) return cout << x, (void)0;
#define deb(x) cerr << (#x) << " is: " << x << endl << flush;
const int INF = 2e9;
const int MOD = 1e9+7;
const int MAXN = 1e5+5;
struct dsu{
    int n;
    vector<int> par, sz;
    dsu(int size) : n(size), par(n+1), sz(n+1) {
        for(int i = 0; i <= n; i++) par[i] = i, sz[i] = 1; 
    }
    int find(int v){ return (par[v]==v?v:par[v]=find(par[v])); }
    bool merge(int a, int b){a = find(a), b = find(b); if(a == b) return false; if(sz[a] > sz[b]) swap(a, b); par[a] = b, sz[b] += sz[a]; return true; }
};
vector<int> adj[MAXN];
int lo[MAXN], h[MAXN];
bool mark[MAXN];
multiset<pii> cut;
void dfs(int v, int p){
    mark[v] = true, lo[v] = h[v];
    for(int u : adj[v]) if(u != p){
        if(!mark[u]) h[u] = h[v]+1, dfs(u, v);
        lo[v] = min(lo[v], lo[u]);
        if(lo[u] > h[v]) 
            cut.emplace(v, u);
    }
}
void solve(){
    int n, m; cin >> n >> m;
    dsu t1(n), t2(n);
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        if(t1.merge(u, v) || t2.merge(u, v))
            adj[u].pb(v), adj[v].pb(u);
    }
    for(int i = 1; i <= n; i++)
        if(!mark[i]) dfs(i, -1);
    for(pii e : cut){
        if(cut.count(e) > 1) continue;
        else cout << e.F << ' ' << e.S << endl;
    }
}

int32_t main(){
    cin.tie(0) -> sync_with_stdio(false);
    int tc = 1;
    //cin >> tc;
    while(tc--) solve();
}

• 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