oj.uz

Submission #1055533

# Submission time Handle Problem Language Result Execution time Memory
1055533 2024-08-12T21:12:12 Z Edu175 Pipes (CEOI15_pipes) C++17
90 / 100
 706 ms 30360 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=5e4;
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 4 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 54 ms 7164 KB Output is correct
2 Correct 51 ms 6992 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 7740 KB Output is correct
2 Correct 103 ms 7180 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 8648 KB Output is correct
2 Correct 129 ms 8444 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 11152 KB Output is correct
2 Correct 170 ms 10032 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 12268 KB Output is correct
2 Correct 343 ms 12332 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 13728 KB Output is correct
2 Correct 375 ms 11712 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 13900 KB Output is correct
2 Correct 507 ms 12452 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 13700 KB Output is correct
2 Runtime error 706 ms 30360 KB Memory limit exceeded
3 Halted 0 ms 0 KB -