Submission #142704

#	Time	Username	Problem	Language	Result	Execution time	Memory
142704		Anai	Pipes (CEOI15_pipes)	C++14	50 / 100	5028 ms	65536 KiB

pipes

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, M = 6e6 + 5, LG = 17;

vector<int> g[N];
int dsu[N], lvl[N], accm[N], far[LG][N];

bitset<M> edgs(0);
int n, m, lptr;

static int get_dsu(int nod) {
	return (dsu[nod] ? (dsu[nod] = get_dsu(dsu[nod])) : nod); }

static bool join(int a, int b) {
	a = get_dsu(a);
	b = get_dsu(b);
	if (a == b)
		return false;
	if (rand() % 2)
		swap(a, b);
	dsu[a] = b;
	return true; }

static void dfs(int u, int pap = 0) {
	far[0][u] = pap;
	lvl[u] = lvl[pap] + 1;
	for (auto v: g[u]) if (v != pap)
		dfs(v, u); }

static void build_rmq() {
	for (int lg = 1; lg < LG; ++lg)
	for (int u = 1; u <= n; ++u)
		far[lg][u] = far[lg - 1][far[lg - 1][u]]; }

static int lca(int a, int b) {
	if (lvl[a] < lvl[b])
		swap(a, b);
	for (int lg = 0; lg < LG; ++lg)
		if ((lvl[a] - lvl[b]) & (1 << lg))
			a = far[lg][a];
	if (a == b)
		return a;
	for (int lg = LG - 1; lg >= 0; --lg)
		if (far[lg][a] != far[lg][b]) {
			a = far[lg][a];
			b = far[lg][b]; }
	return far[0][a]; }

static void answer(int nod, int pap = 0) {
	for (auto v: g[nod]) if (v != pap) {
		answer(v, nod);
		accm[nod]+= accm[v]; }
	if (!accm[nod] && pap != 0)
		cout << nod << ' ' << pap << '\n'; }

int main() {
#ifdef HOME
	freopen("pipes.in", "r", stdin);
	freopen("pipes.out", "w", stdout);
#else
	srand(time(NULL));
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int a, b, i = 0; i < m; ++i) {
		cin >> a >> b;
		if (join(a, b)) {
			edgs[i] = true;
			g[a].push_back(b);
			g[b].push_back(a); } }

	rewind(stdin);

	for (int i = 1; i <= n; ++i)
		if (!lvl[i])
			dfs(i);

	build_rmq();

	cin >> n >> m;
	for (int a, b, i = 0; i < m; ++i)  {
		cin >> a >> b;
		if (!edgs[i]) {
			accm[a]+= 1, accm[b]+= 1;
			accm[lca(a, b)]-= 2; } }

	for (int i = 1; i <= n; ++i)
		if (lvl[i] == 1)
			answer(i);

	return 0; }

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10