oj.uz

Submission #243933

# Submission time Handle Problem Language Result Execution time Memory
243933 2020-07-02T08:56:50 Z errorgorn Pipes (CEOI15_pipes) C++14
60 / 100
 1374 ms 8312 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫
 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
 
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
 
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}
 
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
struct ufds{
	int p[100005];
	int v[100005];
	
	ufds(){
		rep(x,0,100005) p[x]=x;
	}
	
	int parent(int i){return (p[i]==i?i:p[i]=parent(p[i]));}
	void unions(int i,int j){p[j]=i;}
} dsu1=ufds(),dsu2=ufds();
 
ii format(int i,int j){
	if (i<j) return ii(i,j);
	else return ii(j,i);
}
 
int n,m;
vector<int> al[100005];
 
int parent[100005];
int depth[100005];
 
void dfs(int i,int p){
	parent[i]=p;
	dsu2.p[i]=i;
 
	for (auto &it:al[i]){
		if (it==p) continue;
		
		depth[it]=depth[i]+1;
		dfs(it,i);
	}
	
	dsu2.v[dsu2.parent(i)]=i;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	
	rep(x,1,n+1){
		dsu1.v[x]=1;
		dsu2.v[x]=x;
	}
	
	int a,b;
	int pa,pb;
	rep(x,0,m){
		cin>>a>>b;
		
		pa=dsu1.parent(a);
		pb=dsu1.parent(b);
		
		if (pa!=pb){
			if (dsu1.v[pa]<dsu1.v[pb]){
				swap(a,b);
				swap(pa,pb);
			}
			
			dsu1.unions(pa,pb);
			dsu1.v[pa]+=dsu1.v[pb];
			
			al[a].push_back(b);
			al[b].push_back(a);
			
			depth[b]=depth[a]+1;
			dfs(b,a);
		}
		else{
			a=dsu2.v[dsu2.parent(a)],b=dsu2.v[dsu2.parent(b)];
			while (a!=b){
				if (depth[a]<depth[b]) swap(a,b);
				
				dsu2.unions(parent[a],a);
				
				a=dsu2.parent(a);
			}
		}
	}
	
	//for (auto &it:bad) cout<<it.fi<<" "<<it.se<<endl;
	
	rep(x,1,n+1){
		for (auto &it:al[x]) if (x<it && dsu2.parent(x)!=dsu2.parent(it)){
			cout<<x<<" "<<it<<endl;
		}
	}
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 3584 KB Output is correct
2 Correct 111 ms 3704 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 3968 KB Output is correct
2 Correct 214 ms 4088 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 4728 KB Output is correct
2 Correct 261 ms 4856 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 6776 KB Output is correct
2 Correct 425 ms 6776 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 667 ms 7416 KB Output is correct
2 Correct 670 ms 7444 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 887 ms 8184 KB Output is correct
2 Incorrect 874 ms 8312 KB Wrong number of edges

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1154 ms 8184 KB Output is correct
2 Incorrect 1118 ms 8244 KB Wrong number of edges

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1374 ms 8056 KB Output is correct
2 Correct 1361 ms 8184 KB Output is correct