oj.uz

Submission #385502

# Submission time Handle Problem Language Result Execution time Memory
385502 2021-04-04T13:45:25 Z MahdiBahramian Pipes (CEOI15_pipes) C++11
60 / 100
 1438 ms 24044 KB 
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define make make_pair
using namespace std;
const int Max = 1e5 + 10;

int par[Max][2];
vector<pair<int , int>> N[Max];
int h[Max]; bool seen[Max];
vector<pair<int , int>> E;

int PAR(int a , int k)
{
	if(par[a][k] == a) return a;
	return par[a][k] = PAR(par[a][k] , k);
}
bool UNI(int a , int b , bool k)
{
	a = PAR(a , k);
	b = PAR(b , k);
	if(a == b) return 0;
	par[a][k] = b;
	return 1;
}
int DFS(int v , int e , int p)
{
	seen[v] = 1;
	int mn = Max;
	for(pair<int , int> u : N[v])
		if(!seen[u.F]) h[u.F] = h[v] + 1 , mn = min(DFS(u.F , u.S , v) , mn);
		else if(u.S != e) mn = min(mn , h[u.F]);
	if(mn >= h[v]) E.pb(make(p , v));
	return mn;
}
int main()
{
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
	int n , m; cin >> n >> m;
	for(int i = 1 ; i <= n ; i++) par[i][0] = par[i][1] = i;
	for(int i = 1 ; i <= m ; i++)
	{
		int a , b; cin >> a >> b;
		if(UNI(a , b , 0) || UNI(a , b , 1)) N[a].pb(make(b , i)) , N[b].pb(make(a , i));
	}
	for(int v = 1 ; v <= n ; v++)
		if(!seen[v])
			DFS(v , 0 , v);
	//cout << '\n';
	for(pair<int , int> e : E)
		if(e.F != e.S)cout << e.F << ' ' << e.S << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 8628 KB Output is correct
2 Correct 130 ms 8300 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 13548 KB Output is correct
2 Correct 231 ms 14828 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 12804 KB Output is correct
2 Correct 448 ms 9388 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 754 ms 14900 KB Output is correct
2 Correct 663 ms 11220 KB Output is correct

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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