Submission #82354

#	Time	Username	Problem	Language	Result	Execution time	Memory
82354		aminra	Pipes (CEOI15_pipes)	C++14	50 / 100	2438 ms	19384 KiB

pipes

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10