Submission #385190

#	Time	Username	Problem	Language	Result	Execution time	Memory
385190		RohamIzadidoost	Pipes (CEOI15_pipes)	C++14	10 / 100	1318 ms	21612 KiB

pipes

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10