oj.uz

Submission #1055522

# Submission time Handle Problem Language Result Execution time Memory
1055522 2024-08-12T21:04:03 Z Edu175 Pipes (CEOI15_pipes) C++17
40 / 100
 665 ms 53476 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);
	}
	vector<ii>edi;
	while(SZ(ed)){
		ll i=SZ(ed)-1;
		if(br[i])edi.pb(ed[i]);
		else uf_join(ed[i].fst,ed[i].snd);
		ed.pop_back();
	}
	swap(ed,edi);
	// fore(i,0,n)cout<<lw[i]<<" ";;cout<<"\n";
	fore(i,0,n){
		g[i].clear();
	}
}
int main(){FIN;
	mset(uf,-1);
	ll m; cin>>n>>m;
	ll K=40,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 3 ms 4440 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4952 KB Output is correct
2 Correct 6 ms 4956 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8544 KB Output is correct
2 Correct 55 ms 8096 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 11620 KB Output is correct
2 Correct 110 ms 12016 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 155 ms 16476 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 211 ms 22060 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 325 ms 29528 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 398 ms 36964 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 530 ms 44276 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 665 ms 53476 KB Memory limit exceeded
2 Halted 0 ms 0 KB -