Submission #358573

#	Time	Username	Problem	Language	Result	Execution time	Memory
358573		luciocf	Pipes (CEOI15_pipes)	C++14	0 / 100	5053 ms	65540 KiB

pipes

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 1e3+10;

struct DSU
{
	int pai[maxn], peso[maxn];

	void init(int n)
	{
		for (int i = 1; i <= n; i++)
			pai[i] = i, peso[i] = 1;
	}

	int Find(int x)
	{
		if (pai[x] == x) return x;
		return pai[x] = Find(pai[x]);
	}

	void Join(int x, int y)
	{
		x = Find(x), y = Find(y);
		if (x == y) return;

		if (peso[x] < peso[y]) swap(x, y);

		pai[y] = x, peso[x] += peso[y];
	}
} dsu, dsu2;

pii edge[maxn], old[maxn];

set<pii> st;

void walk(int u, int v)
{
	vector<int> path_u, path_v;

	while (true)
	{
		path_u.push_back(u);

		if (!edge[u].ss) break;
		u = dsu.Find(edge[u].ss);
	}

	while (true)
	{
		path_v.push_back(v);

		if (!edge[v].ss) break;
		v = dsu.Find(edge[v].ss);
	}

	int lca, ptr_u = path_u.size()-1, ptr_v = path_v.size()-1;

	while (ptr_u >= 0 && ptr_v >= 0 && path_u[ptr_u] == path_v[ptr_v])
	{
		lca = path_u[ptr_u];
		ptr_u--, ptr_v--;
	}

	ptr_u++, ptr_v++;

	pii pp = edge[lca];

	for (int i = 0; i < ptr_u; i++)
	{
		pii e = edge[path_u[i]];

		if (st.count(e)) st.erase(e);
		if (st.count({e.ss, e.ff})) st.erase({e.ss, e.ff});

		dsu.Join(path_u[i], path_u[i+1]);
	}

	for (int i = 0; i < ptr_v; i++)
	{
		pii e = edge[path_v[i]];

		if (st.count(e)) st.erase(e);
		if (st.count({e.ss, e.ff})) st.erase({e.ss, e.ff});

		dsu.Join(path_v[i], path_v[i+1]);
	}

	edge[dsu.Find(lca)] = pp;
}

void makeroot(int u)
{
	bool end = 0;
	if (edge[u].ss == 0) return;

	old[u] = edge[u];

	while (!end)
	{
		int next_u = dsu.Find(edge[u].ss);
		end |= (!edge[next_u].ss);

		old[next_u] = edge[next_u];
		edge[next_u] = {old[u].ss, old[u].ff};

		u = next_u;
	}
}

int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);

	dsu.init(n); dsu2.init(n);

	for (int i = 1; i <= m; i++)
	{
		int u, v;
		scanf("%d %d", &u, &v);

		int fu = dsu.Find(u), fv = dsu.Find(v);

		if (fu == fv) continue;

		if (dsu2.Find(fu) == dsu2.Find(fv)) walk(fu, fv);
		else
		{
			st.insert({u, v});

			int cu = dsu2.Find(fu), cv = dsu2.Find(fv);

			if (dsu2.peso[cu] > dsu2.peso[cv])
			{
				makeroot(fv);
				edge[fv] = {v, u};
			}
			else
			{
				makeroot(fu);
				edge[fu] = {u, v};
			}

			dsu2.Join(fu, fv);
		}
	}

	for (auto pp: st)
		printf("%d %d\n", pp.ff, pp.ss);
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:120:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp: In function 'void walk(int, int)':
pipes.cpp:63:6: warning: 'lca' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |  int lca, ptr_u = path_u.size()-1, ptr_v = path_v.size()-1;
      |      ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 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