oj.uz

Submission #1055535

# Submission time Handle Problem Language Result Execution time Memory
1055535 2024-08-12T21:12:50 Z Edu175 Pipes (CEOI15_pipes) C++17
100 / 100
 903 ms 12512 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,mxcon=b;i<mxcon;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);;cout.tie(0);
#define imp(v) {for(auto kjdfhg:v)cout<<kjdfhg<<" ";cout<<"\n";}
using namespace std;
typedef int ll;
typedef pair<ll,ll> ii;
const ll MAXN=1e5+5,MAXM=6e6+5;
ll uf[MAXN];
ll uf_find(ll x){return uf[x]<0?x:uf[x]=uf_find(uf[x]);}
void uf_join(ll x, ll y){
	x=uf_find(x),y=uf_find(y);
	if(x==y)return;
	if(uf[x]>uf[y])swap(x,y);
	uf[x]+=uf[y],uf[y]=x;
}
bitset<MAXM> vised,br;
bitset<MAXN> vis;
ll lw[MAXN],D[MAXN];
vector<ii> g[MAXN];
vector<ii>ed;
void dfs(ll x){
	// cout<<"dfs "<<x<<" "<<fa<<"\n";
	vis[x]=1;
	lw[x]=D[x];
	for(auto [y,i]:g[x])if(!vised[i]){
		vised[i]=1;
		if(!vis[y]){
			D[y]=D[x]+1;
			dfs(y);
			if(lw[y]>=D[y])br[i]=1;//,cout<<"tree ";
			lw[x]=min(lw[x],lw[y]);
		}
		else {
			lw[x]=min(lw[x],D[y]);
			// cout<<"back ";
		}
		// cout<<x<<" "<<y<<"\n";
	}
}
ll n;
void doit(){
	vised.reset();
	vis.reset();
	br.reset();
	fore(i,0,SZ(ed)){
		auto [u,v]=ed[i];
		u=uf_find(u); v=uf_find(v);
		if(u==v)continue;
		g[u].pb({v,i});
		g[v].pb({u,i});
	}
	fore(i,0,n)if(!vis[i]){
		D[i]=0;
		dfs(i);
	}
	fore(i,0,n){
		g[i].clear();
	}
	
	vector<ii>edi;
	while(SZ(ed)){
		auto i=SZ(ed)-1;
		if(br[i])edi.pb(ed[i]);
		else uf_join(ed[i].fst,ed[i].snd);
		ed.pop_back();
	}
	// fore(i,0,SZ(ed)){
	// }
	swap(ed,edi);
	// fore(i,0,n)cout<<lw[i]<<" ";;cout<<"\n";
}
const ll MK=25e3;
int main(){FIN;
	mset(uf,-1);
	ll m; cin>>n>>m;
	// ll K=100,MK=(m+K-1)/K;
	fore(i,0,m){
		ll u,v; cin>>u>>v; u--,v--;
		ed.pb({u,v});
		if(i==m-1||i%MK==MK-1)doit();
	}
	for(auto [u,v]:ed)cout<<u+1<<" "<<v+1<<"\n";
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 6100 KB Output is correct
2 Correct 56 ms 5916 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 6504 KB Output is correct
2 Correct 105 ms 6096 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 7072 KB Output is correct
2 Correct 136 ms 7664 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 9384 KB Output is correct
2 Correct 179 ms 8884 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 10304 KB Output is correct
2 Correct 402 ms 11680 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 11876 KB Output is correct
2 Correct 417 ms 11068 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 11832 KB Output is correct
2 Correct 522 ms 11072 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 11320 KB Output is correct
2 Correct 903 ms 12512 KB Output is correct