Submission #113032

#	Time	Username	Problem	Language	Result	Execution time	Memory
113032		Mahdi_Jfri	Pipes (CEOI15_pipes)	C++14	100 / 100	1172 ms	13248 KiB

pipes

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e5 + 20;

struct dsu
{
	int p[maxn];

	dsu()
	{
		memset(p , -1 , sizeof p);
	}

	int root(int v)
	{
		return (p[v] < 0? v : p[v] = root(p[v]));
	}

	bool merge(int v , int u)
	{
		v = root(v) , u = root(u);
		if(v == u)
			return 0;

		if(-p[v] < -p[u])
			swap(v , u);

		p[v] += p[u];
		p[u] = v;
		return 1;
	}
};

dsu tree , tc;

int dp[maxn] , h[maxn];

bool visited[maxn];

vector<int> adj[maxn];

void dfs(int v , int p = -1)
{
	visited[v] = 1;
	dp[v] = h[v];

	bool seen = 0;
	for(auto u : adj[v])
	{
		if(!visited[u])
		{
			h[u] = h[v] + 1;
			dfs(u , v);
			dp[v] = min(dp[v] , dp[u]);
		}
		else if(h[u] < h[v] - 1 || seen)
			dp[v] = min(dp[v] , h[u]);

		seen |= (u == p);
	}

	if(p != -1 && dp[v] >= h[v])
		cout << v + 1 << " " << p + 1 << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n , m;
	cin >> n >> m;

	for(int i = 0; i < m; i++)
	{
		int a , b;
		cin >> a >> b;
		a-- , b--;

		if(tree.merge(a , b) || tc.merge(a , b))
			adj[a].pb(b) , adj[b].pb(a);
	}

	for(int i = 0; i < n; i++)
		if(!visited[i])
			dfs(i);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10