oj.uz

Submission #358586

# Submission time Handle Problem Language Result Execution time Memory
358586 2021-01-25T22:46:14 Z luciocf Pipes (CEOI15_pipes) C++14
50 / 100
 1341 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];

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];
	edge[lca] = {0, 0};

	for (int i = 0; i <= ptr_u; i++)
	{
		edge[path_u[i]] = {0, 0};
		dsu.Join(path_u[i], lca);
	}

	for (int i = 0; i <= ptr_v; i++)
	{
		edge[path_v[i]] = {0, 0};
		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
		{
			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 (int i = 1; i <= n; i++)
		if (edge[i].ff)
			printf("%d %d\n", edge[i].ff, edge[i].ss);
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp: In function 'void walk(int, int)':
pipes.cpp:61:6: warning: 'lca' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |  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 4 ms 492 KB Output is correct
2 Correct 4 ms 492 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 492 KB Output is correct
2 Correct 121 ms 508 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 1132 KB Output is correct
2 Correct 283 ms 15468 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 2540 KB Output is correct
2 Runtime error 381 ms 20744 KB Memory limit exceeded

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 2796 KB Output is correct
2 Runtime error 672 ms 36460 KB Memory limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 854 ms 3436 KB Output is correct
2 Runtime error 872 ms 44924 KB Memory limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1098 ms 3436 KB Output is correct
2 Runtime error 1059 ms 56652 KB Memory limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1341 ms 12524 KB Output is correct
2 Runtime error 1316 ms 65536 KB Memory limit exceeded