oj.uz

Submission #874396

# Submission time Handle Problem Language Result Execution time Memory
874396 2023-11-16T20:48:22 Z Hamed_Ghaffari Pipes (CEOI15_pipes) C++17
100 / 100
 881 ms 16024 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long       ll;
typedef pair<int, int>  pii;

#define FastIO          cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define FileIO          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define F               first
#define S               second
#define max_heap(T)     priority_queue<T>
#define min_heap(T)     priority_queue<T, vector<T>, greater<T>>
#define fr(i,a,b)       for(int i=a;i<b;i++)
#define frr(i,a,b)      for(int i=a;i>b;i--)
#define frin(i,A)       for(auto &i : A)
#define frp(a,b,A)      for(auto [a, b] : A)
#define SZ(x)           (int)x.size()
#define all(A)          A.begin(), A.end()
#define mins(a,b)       a = min(a,b)
#define maxs(a,b)       a = max(a,b)
#define pb              push_back
#define kill(x)         cout << x << '\n', exit(0)
#define md(a)           (a%MOD+MOD)%MOD

const ll  INF  = 2e9;
const ll  MOD  = 1e9 + 7;
const int MAXN = 1e5 + 1;
const int LOG  = 30;

int n, m, par0[MAXN], par1[MAXN], hi[MAXN], mn[MAXN], edge;
vector<pii> g[MAXN];

int Find0(int v) { return v == par0[v] ? v : par0[v] = Find0(par0[v]); }
int Find1(int v) { return v == par1[v] ? v : par1[v] = Find1(par1[v]); }
bool Union(int u, int v) {
	int u0 = Find0(u), v0 = Find0(v);
	if(u0 == v0) {
		int u1 = Find1(u), v1 = Find1(v);
		if(u1 == v1)
			return 0;
		par1[u1] = v1;
		edge++;
		return 1;
	}
	par0[u0] = v0;
	edge++;
	return 1;
}

void dfs(int v, int p, int pid) {
	hi[v] = hi[p]+1;
	mn[v] = hi[v];
	frin(u, g[v]) {
		if(u.F == p && u.S == pid)
			continue;
		if(!hi[u.F])
			dfs(u.F, v, u.S);
		mins(mn[v], mn[u.F]);
	}
	if(v != p && mn[v] == hi[v])
		cout << v << ' ' << p << '\n';
}

void solve() {
	cin >> n >> m;
	fr(i, 1, n+1)
		par0[i] = par1[i] = i;
	int u, v;
	while(m--) {
		cin >> u >> v;
		if(Union(u, v))
			g[u].pb({v, edge}), g[v].pb({u, edge});
	}
	fr(i, 1, n+1)
		if(!hi[i])
			dfs(i, i, 0);
}

int32_t main() {
	FastIO
	int T = 1;
	// cin >> T;
	while(T--)
		solve();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3420 KB Output is correct
2 Correct 3 ms 3164 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 3156 KB Output is correct
2 Correct 68 ms 3060 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 3996 KB Output is correct
2 Correct 142 ms 3484 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 5952 KB Output is correct
2 Correct 192 ms 5252 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 11916 KB Output is correct
2 Correct 267 ms 8788 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 13400 KB Output is correct
2 Correct 431 ms 9676 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 16024 KB Output is correct
2 Correct 544 ms 11208 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 15960 KB Output is correct
2 Correct 719 ms 11128 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 881 ms 15184 KB Output is correct
2 Correct 824 ms 11432 KB Output is correct