oj.uz

Submission #224074

# Submission time Handle Problem Language Result Execution time Memory
224074 2020-04-17T07:35:11 Z kshitij_sodani Pipes (CEOI15_pipes) C++17
0 / 100
 1454 ms 30456 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<int> adj[100001];
vector<pair<int,int>> ans;
int cco=1;
void dfs(int no,int par3=-1){
	par[no]=cco;
	cco+=1;
	int co=0;
//	cout<<no<<endl;
	vector<int> kk;
	for(auto nn:adj[no]){
		if(par[nn]>0){

		//	cout<<no<<",:<:"<<nn<<endl;
			if(nn==par3 or par[nn]>=par[no]){
				continue;
			}
	//		cout<<no<<",:<:"<<nn<<endl;
			par2[nn]-=1;
			co+=1;
		}
		else{
			int xx=par2[no];
			dfs(nn,no);
			if(par2[nn]==0){
				cout<<no+1<<" "<<nn+1<<endl;

			}
			kk.pb(nn);

		/*	if(par2[nn]+par2[no]==0){
				cout<<no+1<<"::"<<nn+1<<endl;
			}*/
		}
	}
	//cout<<no<<",..,"<<par2[no]<<endl;
/*	for(auto nn:kk){
		if(par2[nn]+par2[no]==0){
			cout<<no+1<<"::"<<nn+1<<endl;
		}

	}*/
	for(auto nn:kk){
		par2[no]+=par2[nn];
	}
	
	par2[no]+=co;
//	cout<<no<<",,"<<par2[no]<<endl;
}
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;
	for(int i=0;i<m;i++){
		cin>>cc>>dd;
		cc-=1;
		dd-=1;
		//cout<<cc<<" "<<dd<<endl;
		aa=find(cc);
	//	cout<<aa;
		bb=find(dd);
	//	cout<<"::"<<bb<<endl;
		if(aa==bb){
			e=find2(cc);
			f=find2(dd);
			if(e==f){
				continue;
			}
			adj[cc].pb(dd);
			adj[dd].pb(cc);
			par2[e]=f;
		}
		else{
			par[aa]=bb;
			adj[cc].pb(dd);
			adj[dd].pb(cc);
		}
	//	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;
}

Compilation message

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:45:8: warning: unused variable 'xx' [-Wunused-variable]
    int xx=par2[no];
        ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Incorrect 6 ms 2688 KB Wrong number of edges

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3328 KB Output is correct
2 Incorrect 10 ms 3072 KB Wrong number of edges

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 8568 KB Output is correct
2 Incorrect 117 ms 8276 KB Wrong number of edges

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 13560 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 325 ms 19136 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 491 ms 30456 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 15584 KB Output is correct
2 Incorrect 685 ms 11744 KB Wrong number of edges

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 964 ms 19192 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1229 ms 23576 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1454 ms 25824 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -