oj.uz

Submission #385503

# Submission time Handle Problem Language Result Execution time Memory
385503 2021-04-04T13:47:13 Z MahdiBahramian Pipes (CEOI15_pipes) C++17
90 / 100
 1362 ms 19180 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 2688 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 3180 KB Output is correct
2 Correct 109 ms 3012 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 3960 KB Output is correct
2 Correct 230 ms 3440 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 5784 KB Output is correct
2 Runtime error 323 ms 19180 KB Memory limit exceeded

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 11968 KB Output is correct
2 Correct 399 ms 8424 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 13420 KB Output is correct
2 Correct 659 ms 9708 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 958 ms 15724 KB Output is correct
2 Correct 839 ms 13292 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1117 ms 15724 KB Output is correct
2 Correct 1050 ms 15596 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1362 ms 15128 KB Output is correct
2 Correct 1245 ms 14860 KB Output is correct