oj.uz

Submission #874390

# Submission time Handle Problem Language Result Execution time Memory
874390 2023-11-16T20:34:17 Z Hamed_Ghaffari Pipes (CEOI15_pipes) C++17
10 / 100
 779 ms 65536 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 + 5;
const int LOG  = 30;

int n, m, par[MAXN][2], hi[MAXN];
vector<int> g[MAXN];

void DSU() {
	fr(i, 1, n+1)
		par[i][0] = par[i][1] = i;
}
int Find(int v, int x) { return v == par[v][x] ? v : par[v][x] = Find(par[v][x], x); }
void Union(int u, int v) {
	if(Find(u, 0) != Find(v, 0)) {
		par[Find(u, 0)][0] = Find(v, 0);
		g[u].pb(v);
		g[v].pb(u);
		return;
	}
	if(Find(u, 1) != Find(v, 1)) {
		par[Find(u, 1)][1] = Find(v, 1);
		g[u].pb(v);
		g[v].pb(u);
		return;
	}
}

int dfs(int v, int p) {
	hi[v] = hi[p]+1;
	int res = hi[v];
	frin(u, g[v])
		if(u == p)
			continue;
		else if(!hi[u])
			mins(res, dfs(u, v));
		else if(hi[u] < hi[v])
			mins(res, hi[u]);
	if(v != p && res == hi[v])
		cout << min(v, p) << ' ' << max(v, p) << '\n';
	return res;
}

void solve() {
	cin >> n >> m;
	DSU();
	int u, v;
	while(m--) {
		cin >> u >> v;
		Union(u, v);
	}
	fr(i, 1, n+1)
		if(!hi[i])
			dfs(i, i);
}

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 1 ms 2652 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3164 KB Output is correct
2 Incorrect 3 ms 2864 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 2968 KB Output is correct
2 Incorrect 64 ms 2972 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 3772 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 5220 KB Output is correct
2 Correct 162 ms 4940 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 10452 KB Output is correct
2 Runtime error 241 ms 24436 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 11540 KB Output is correct
2 Runtime error 388 ms 40528 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 13648 KB Output is correct
2 Runtime error 506 ms 48168 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 13460 KB Output is correct
2 Runtime error 629 ms 59028 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 12952 KB Output is correct
2 Runtime error 758 ms 65536 KB Memory limit exceeded
3 Halted 0 ms 0 KB -