oj.uz

Submission #113032

# Submission time Handle Problem Language Result Execution time Memory
113032 2019-05-23T07:42:55 Z Mahdi_Jfri Pipes (CEOI15_pipes) C++14
100 / 100
 1172 ms 13248 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3840 KB Output is correct
2 Correct 7 ms 3712 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3832 KB Output is correct
2 Correct 94 ms 3704 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 4420 KB Output is correct
2 Correct 187 ms 3964 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 5760 KB Output is correct
2 Correct 235 ms 5500 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 10324 KB Output is correct
2 Correct 335 ms 7416 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 11248 KB Output is correct
2 Correct 558 ms 8860 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 13152 KB Output is correct
2 Correct 778 ms 9084 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 13248 KB Output is correct
2 Correct 924 ms 9236 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1172 ms 12700 KB Output is correct
2 Correct 1099 ms 10196 KB Output is correct