oj.uz

Submission #224134

# Submission time Handle Problem Language Result Execution time Memory
224134 2020-04-17T08:44:26 Z kshitij_sodani Pipes (CEOI15_pipes) C++17
100 / 100
 1516 ms 15536 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
int n,m;
int par[100001];
int par2[100001];
int find(int no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
int find2(int no){
	if(par2[no]==no){
		return no;
	}
	par2[no]=find2(par2[no]);
	return par2[no];
}
vector<pair<int,int>> adj[100001];
int cco=1;

void dfs(int no,int par3=-1){
	par[no]=cco;
	cco+=1;
	for(auto nn:adj[no]){
		if(par[nn.a]>0){
			if(nn.b==par3){
				continue;
			}
			if(par[nn.a]>=par[no]){
				continue;
			}
			par2[nn.a]-=1;
			par2[no]+=1;
		}
		else{
			dfs(nn.a,nn.b);
			if(par2[nn.a]==0){
			//	if(kk[{no,nn.a}]==1){
					cout<<no+1<<" "<<nn.a+1<<endl;
			//	}
			}
			par2[no]+=par2[nn.a];
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		par[i]=i;
		par2[i]=i;
	}
	int aa,bb;
	int cc,dd;
	int e,f;
	int ind=0;
	for(int i=0;i<m;i++){
		cin>>cc>>dd;
		cc-=1;
		dd-=1;

		aa=find(cc);
		bb=find(dd);
		/*if(kk[{cc,dd}]==1){
			kk[{cc,dd}]+=1;
			kk[{dd,cc}]+=1;

		}*/
		if(aa==bb){
			e=find2(cc);
			f=find2(dd);
			if(e==f){
				continue;
			}
			adj[cc].pb({dd,ind});
			adj[dd].pb({cc,ind});
		/*	kk[{cc,dd}]+=1;
			kk[{dd,cc}]+=1;*/
			par2[e]=f;
			ind+=1;
		}
		else{
			par[aa]=bb;
			adj[cc].pb({dd,ind});
			adj[dd].pb({cc,ind});
		/*	kk[{cc,dd}]+=1;
			kk[{dd,cc}]+=1;*/
			ind+=1;
		}


	//	cout<<cc<<",,,,,,,,"<<dd<<endl;
	}
	//vis=par
	//dp=par2
	for(int i=0;i<n;i++){
		par[i]=0;
		par2[i]=0;
	}
	for(int i=0;i<n;i++){
		if(par[i]==0){
			dfs(i);
		}
	}
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3328 KB Output is correct
2 Correct 10 ms 3200 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 3704 KB Output is correct
2 Correct 115 ms 3960 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 4392 KB Output is correct
2 Correct 239 ms 3928 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 6652 KB Output is correct
2 Correct 308 ms 6008 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 11640 KB Output is correct
2 Correct 445 ms 9020 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 763 ms 12664 KB Output is correct
2 Correct 729 ms 10104 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1033 ms 15356 KB Output is correct
2 Correct 952 ms 11336 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1299 ms 15480 KB Output is correct
2 Correct 1171 ms 11256 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1516 ms 15536 KB Output is correct
2 Correct 1468 ms 10488 KB Output is correct