oj.uz

Submission #385505

# Submission time Handle Problem Language Result Execution time Memory
385505 2021-04-04T13:50:25 Z MahdiBahramian Pipes (CEOI15_pipes) C++14
100 / 100
 1317 ms 15628 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];
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)
{
	int mn = Max;
	for(pair<int , int> u : N[v])
		if(!h[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(!h[v])
			h[v] = 1 , 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 3308 KB Output is correct
2 Correct 6 ms 3052 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 3180 KB Output is correct
2 Correct 108 ms 3052 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 4076 KB Output is correct
2 Correct 216 ms 3436 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 5868 KB Output is correct
2 Correct 260 ms 5228 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 11904 KB Output is correct
2 Correct 432 ms 8428 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 13164 KB Output is correct
2 Correct 638 ms 9580 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 891 ms 15628 KB Output is correct
2 Correct 841 ms 10760 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1089 ms 15596 KB Output is correct
2 Correct 1022 ms 10732 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1317 ms 15056 KB Output is correct
2 Correct 1216 ms 11284 KB Output is correct