Submission #1173558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173558		Dan4Life	Pipes (CEOI15_pipes)	C++20	100 / 100	549 ms	14756 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using ar2 = array<ll,2>;
using vi = vector<int>;
const int mxN = (int)1e5+10;
const ll INF = (int)1e9;
const ll MOD = (ll)1e6+7;
 
template<int SZ> struct Dsu{
	int p[SZ], sz[SZ];
	
	void init(int n=SZ-1){
		for(int i = 1; i <= n; i++) p[i]=i,sz[i]=1;
	}
	int findSet(int i){return i==p[i]?i:p[i]=findSet(p[i]);}
	bool isSameSet(int i, int j){ return findSet(i)==findSet(j); }
	void unionSet(int i, int j){
		int x = findSet(i), y = findSet(j);
		if(x==y) return;
		if(sz[x]<sz[y])swap(x,y);
		p[y] = x, sz[x]+=sz[y];
	}
};
Dsu<mxN> dsu, dsu2;

int n, m, dfs_tim;
vi adj[mxN];
int low[mxN], st[mxN];
 
void dfs(int s, int p){
	st[s]=low[s]=++dfs_tim;
	bool par = 0;
	for(auto u : adj[s]){
		if(u==p and !par){ par=1; continue;}
		if(!st[u]){
			dfs(u,s);
			low[s] = min(low[s], low[u]);
			if(low[u] > st[s]) cout << s << " " << u << "\n";
		}
		else low[s]=min(low[s],st[u]);
	}
}
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m; dsu.init(n), dsu2.init(n);
	for(int i = 0; i < m; i++){
		int a, b,ok=0; cin >> a >> b; 
		if(dsu.isSameSet(a,b)){
			if(!dsu2.isSameSet(a,b))
				dsu2.unionSet(a,b),ok=1;
		}
		else dsu.unionSet(a,b),ok=1;
		if(!ok) continue;
		adj[a].pb(b), adj[b].pb(a);
	}
	for(int i = 1; i <= n; i++){
		if(st[i]) continue;
		dfs_tim = 0; dfs(i,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