oj.uz

Submission #358585

# Submission time Handle Problem Language Result Execution time Memory
358585 2021-01-25T22:39:59 Z luciocf Pipes (CEOI15_pipes) C++14
40 / 100
 1563 ms 65536 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], 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--;
	}

	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], lca);
	}

	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], lca);
	}

	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(old[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

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

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 620 KB Output is correct
2 Correct 7 ms 748 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 5996 KB Output is correct
2 Correct 132 ms 5868 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 10748 KB Output is correct
2 Correct 271 ms 12396 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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