제출 #1081554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081554		42kangaroo	Pipes (CEOI15_pipes)	C++17	30 / 100	1966 ms	65536 KiB

pipes

//
// 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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10