oj.uz

Submission #385190

# Submission time Handle Problem Language Result Execution time Memory
385190 2021-04-03T13:36:54 Z RohamIzadidoost Pipes (CEOI15_pipes) C++14
10 / 100
 1318 ms 21612 KB 
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 1000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
int n , m , par[2][maxn] , sz[2][maxn] , dp[maxn] , p[maxn] , mark[maxn] , h[maxn]; 
vec<int> adj[maxn] ; 
void prep(){
	for(int i = 1 ; i <= n ; i ++ ){
		par[0][i] = par[1][i] = i ; 
		sz[0][i] = sz[1][i] = 1 ; 
	}
}
vec<pii> e ;
int getpar(int k , int v){
	return par[k][v] == v ? v : par[k][v] = getpar(k , par[k][v]) ; 
}
bool merge(int k , int x , int y){
	x = getpar(k , x) ;y = getpar(k , y) ; 
	if(x == y) return false ; 
	if(sz[k][x] < sz[k][y]) swap(x , y) ; 
	sz[k][x] += sz[k][y] ; 
	par[k][y] = x ; 
	return true ; 
}
void dfs(int v){
	mark[v] = 1 ; 
	for(auto u : adj[v]){
		if(!mark[u]){
			p[u] = v ; 
			h[u] = h[v] + 1 ; 
			dfs(u) ;
			dp[v] = min(dp[v] , dp[u]) ;
		}else{
			if(u != p[v]){
				dp[v] = min(dp[v] , h[u]) ;
			}
		}
	}
	if(p[v] != 0 && dp[v] > h[p[v]]){
		cout<<v <<" " << p[v] << endl ; 
	}
	dp[v] = min(dp[v] , h[p[v]] ) ;
}
int main()
{
	migmig ;
	h[0] = mod ; 
	cin>>n>>m ;
	prep() ; 
	int u , v ;  
	for(int i =1  ; i <= m ; i ++ ){
		cin>>u>>v ;
		if(!merge(0 , u , v)){
			if(merge(1 , u , v)){
				adj[u].pb(v) ;
				adj[v].pb(u) ;  
			}
		}else{
			adj[v].pb(u) ; 
			adj[u].pb(v) ; 
		}
	}
	memset(dp , 63 , sizeof dp) ; 
	for(int i = 1 ; i <= n ; i ++ ){
		if(!mark[i]){
			dfs(i) ; 
		}
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3052 KB Output is correct
2 Incorrect 3 ms 3052 KB Wrong number of edges

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3820 KB Output is correct
2 Incorrect 7 ms 3564 KB Wrong number of edges

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 8972 KB Output is correct
2 Incorrect 114 ms 8684 KB Wrong number of edges

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 10860 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 12280 KB Output is correct
2 Correct 270 ms 12396 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 12524 KB Output is correct
2 Incorrect 376 ms 8940 KB Wrong number of edges

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 13976 KB Output is correct
2 Incorrect 627 ms 11244 KB Wrong number of edges

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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