oj.uz

Submission #358587

# Submission time Handle Problem Language Result Execution time Memory
358587 2021-01-25T22:52:53 Z luciocf Pipes (CEOI15_pipes) C++14
100 / 100
 1422 ms 8812 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];
 
	void init(int n)
	{
		for (int i = 1; i <= n; i++)
			pai[i] = i;
	}
 
	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;
 
		pai[y] = x;
	}
} dsu;

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 748 KB Output is correct
2 Correct 254 ms 876 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 1260 KB Output is correct
2 Correct 298 ms 1516 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 2412 KB Output is correct
2 Correct 395 ms 2412 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 709 ms 2668 KB Output is correct
2 Correct 671 ms 2704 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 918 ms 3180 KB Output is correct
2 Correct 876 ms 3308 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1161 ms 3180 KB Output is correct
2 Correct 1100 ms 3180 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1422 ms 3436 KB Output is correct
2 Correct 1340 ms 8812 KB Output is correct