oj.uz

Submission #358568

# Submission time Handle Problem Language Result Execution time Memory
358568 2021-01-25T20:34:02 Z luciocf Pipes (CEOI15_pipes) C++14
0 / 100
 5000 ms 3580 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 1e5+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];

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;	

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

		edge[next_u] = {edge[u].ss, edge[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

pipes.cpp: In function 'int main()':
pipes.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  117 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  124 |   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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5066 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5052 ms 492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5050 ms 492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5045 ms 620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5063 ms 1132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5083 ms 2540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5079 ms 3052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5085 ms 3580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5052 ms 3564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5093 ms 3308 KB Time limit exceeded
2 Halted 0 ms 0 KB -