Submission #243935

#	Time	Username	Problem	Language	Result	Execution time	Memory
243935		errorgorn	Pipes (CEOI15_pipes)	C++14	100 / 100	1830 ms	14072 KiB

pipes

//雪花飄飄北風嘯嘯
//天地一片蒼茫
 
#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];
	
	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 ss[100005];
int depth[100005];
 
set<ii> bad;
 
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);
	}
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	
	rep(x,1,n+1){
		ss[x]=1;
	}
	
	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 (ss[pa]<ss[pb]){
				swap(a,b);
				swap(pa,pb);
			}
			
			dsu1.unions(pa,pb);
			ss[pa]+=ss[pb];
			
			al[a].push_back(b);
			al[b].push_back(a);
			
			depth[b]=depth[a]+1;
			dfs(b,a);
		}
		else{
			a=dsu2.parent(a),b=dsu2.parent(b);
			while (a!=b){
				if (depth[a]<depth[b]) swap(a,b);
				
				bad.insert(format(a,parent[a]));
				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 && !bad.count(ii(x,it))){
			cout<<x<<" "<<it<<endl;
		}
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10