oj.uz

Submission #82354

# Submission time Handle Problem Language Result Execution time Memory
82354 2018-10-30T08:55:28 Z aminra Pipes (CEOI15_pipes) C++14
50 / 100
 2438 ms 19384 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int MAXN = (int)70003;
const int MAXS = (int)2000003;
const int infint = (int)1e9;
const ll inf = (ll)1e18;
int par[MAXN], u[MAXS], v[MAXS], n, m, h[MAXN];
bool val[MAXN];
bool used[MAXS];
vector<int> G[MAXN];
int parent(int u)
{
	return par[u] < 0 ? u : par[u] = parent(par[u]);
}
void merge(int u, int v)
{
	if(par[u] < par[v])
		swap(u, v); //alan size u < size v.
	par[v] += par[u];
	par[u] = v;
}
void dfs(int u, int pa)
{
	par[u] = pa;
	for (auto v : G[u])
		if(v != pa)
		{
			h[v] = h[u] + 1;
			dfs(v, u);
		}
}
void add(int u, int v)
{
	while(u != v)
	{
		if(h[u] > h[v])
		{
			val[u] = 1;
			u = par[u];
		}
		else
		{
			val[v] = 1;
			v = par[v];
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	memset(par, -1, sizeof par);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> u[i] >> v[i];
		if(parent(u[i]) != parent(v[i]))
		{
			merge(parent(u[i]), parent(v[i]));
			used[i] = 1;
			G[u[i]].push_back(v[i]);
			G[v[i]].push_back(u[i]);
		}
	}
	for (int i = 1; i <= n; i++)
		if(par[i] < 0)
			dfs(i, -1);
	for (int i = 0; i < m; i++)
		if(!used[i])
			add(u[i], v[i]);
	
	for (int i = 1; i <= n; i++)
		if(par[i] != -1 && val[i] == 0)
			cout << i << " " << par[i] << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2304 KB Output is correct
2 Correct 3 ms 2276 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2548 KB Output is correct
2 Correct 6 ms 2560 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 7032 KB Output is correct
2 Correct 305 ms 7136 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 10488 KB Output is correct
2 Correct 323 ms 11972 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 14908 KB Output is correct
2 Correct 646 ms 14500 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2438 ms 19384 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 4352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 4324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 4352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 4400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -