oj.uz

Submission #113037

# Submission time Handle Problem Language Result Execution time Memory
113037 2019-05-23T08:29:20 Z ckodser Pipes (CEOI15_pipes) C++14
100 / 100
 1151 ms 7164 KB 
#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll mod=1e9+7;
const ll maxn=1e5+500;
const ll inf=1e9+900;

ll par[2][maxn];
vector<pii> yal;
vector<ll> ger[maxn];
ll dp[maxn];
bool vis[maxn];
ll h[maxn];


ll find_root(bool b,ll v){
    if(par[b][v]==v){
	return v;
    }
    par[b][v]=find_root(b,par[b][v]);
    return par[b][v];
}
bool merge(bool b,ll v,ll u){
    v=find_root(b,v);
    u=find_root(b,u);
    if(v!=u){
	par[b][v]=u;
	return 1;
    }
    return 0;
}

void dfs(ll a,ll par=-1){
    vis[a]=1;
    dp[a]=h[a];
    for(auto t:ger[a]){
	if(t==par)continue;
	pii e=yal[t];
	ll v=find_root(0,e.F);
	ll u=find_root(0,e.S);
	if(a==u)swap(v,u);
	if(vis[u]){
	    dp[a]=min(dp[a],h[u]);
	}else{
	    h[u]=h[v]+1;
	    dfs(u,t);
	    dp[v]=min(dp[v],dp[u]);
	}
    }
    if(dp[a]==h[a] && par!=-1){
	cout<<yal[par].F+1<<' '<<yal[par].S+1<<endl;
    }
}
void solve(ll a){
    dfs(a);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<n;i++){
	par[0][i]=i;
	par[1][i]=i;
    }
    for(ll i=0;i<m;i++){
	ll v,u;
	cin>>v>>u;
	v--;u--;

	ll av=find_root(0,v);
	ll au=find_root(0,u);

	ll bv=find_root(1,v);
	ll bu=find_root(1,u);

	if(av==au){
	    continue;    
	}
	if(bv==bu){
	    merge(0,av,au);
	}else{
	    yal.pb(mp(v,u));
	    merge(1,bv,bu);
	}
    }
    for(ll i=0;i<yal.size();i++){
	pii e=yal[i];
	ger[find_root(0,e.F)].pb(i);
	ger[find_root(0,e.S)].pb(i);
    }
    for(ll i=0;i<n;i++){
	if(par[0][i]==i && !vis[i]){
	    solve(i);
	}
    }
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:96:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0;i<yal.size();i++){
                ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2944 KB Output is correct
2 Correct 6 ms 2916 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 2848 KB Output is correct
2 Correct 104 ms 2844 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 3048 KB Output is correct
2 Correct 186 ms 3032 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 3524 KB Output is correct
2 Correct 270 ms 4116 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 5392 KB Output is correct
2 Correct 321 ms 4752 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 5560 KB Output is correct
2 Correct 559 ms 6264 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 744 ms 5844 KB Output is correct
2 Correct 729 ms 5480 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 999 ms 5852 KB Output is correct
2 Correct 951 ms 5476 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1151 ms 5768 KB Output is correct
2 Correct 1092 ms 7164 KB Output is correct