Submission #113037

#	Time	Username	Problem	Language	Result	Execution time	Memory
113037		ckodser	Pipes (CEOI15_pipes)	C++14	100 / 100	1151 ms	7164 KiB

pipes

#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 (stderr)

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