oj.uz

Submission #1034717

# Submission time Handle Problem Language Result Execution time Memory
1034717 2024-07-25T17:09:12 Z vjudge1 Pipes (CEOI15_pipes) C++17
40 / 100
 710 ms 65536 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 2 ms 3416 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 9232 KB Output is correct
2 Correct 63 ms 8952 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 13912 KB Output is correct
2 Correct 120 ms 15184 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 170 ms 21844 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 225 ms 31664 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 392 ms 45136 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 472 ms 57936 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 574 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 710 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -