oj.uz

Submission #1081559

# Submission time Handle Problem Language Result Execution time Memory
1081559 2024-08-30T07:20:29 Z 42kangaroo Pipes (CEOI15_pipes) C++17
50 / 100
 906 ms 65536 KB 
//
// Created by 42kangaroo on 30/08/2024.
//
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

constexpr int mod = 1e9 + 7;

using g_t = vector<vector<int>>;

int find(int a, vector<int>& p) {
	return a == p[a] ? a : p[a] = find(p[a], p);
}

bool unite(int a, int b, vector<int>& p) {
	a = find(a, p);
	b = find(b, p);
	if (a == b) return false;
	p[a] = b;
	return true;
}

ll dfs(int n, int p, g_t& g, vector<ll>& noV, vector<bool>& vis) {
	vis[n] = true;
	ll re = noV[n];
	for (auto e: g[n]) {
		if (e == p) continue;
		re ^= dfs(e, n, g, noV, vis);
	}
	if (re == 0 && n != p) cout << n + 1 << " " << p + 1 <<  "\n";
	return re;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m; cin >> n >> m;
	vector<int> p(n);
	iota(p.begin(), p.end(), 0);
	vector<ll> noV(n, 0);
	g_t g(n);
	mt19937 rng(0);
	uniform_int_distribution<ll> dI(0, numeric_limits<ll>::max());
	for (int i = 0; i < m; ++i) {
		int a, b; cin >> a >> b;
		--a; --b;
		if (!unite(a, b, p)) {
			ll nu = dI(rng);
			noV[a] ^= nu;
			noV[b] ^= nu;
		} else {
			g[a].push_back(b);
			g[b].push_back(a);
		}
	}
	vector<bool> vis(n, false);
	for (int i = 0; i < n; ++i) {
		if (!vis[i]) dfs(i, i, g, noV, vis);
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 3724 KB Output is correct
2 Correct 87 ms 3408 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 6176 KB Output is correct
2 Correct 157 ms 12372 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 10280 KB Output is correct
2 Correct 182 ms 16216 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 292 ms 25688 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 464 ms 38920 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 607 ms 50812 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 748 ms 62304 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 906 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -