oj.uz

답안 #243932

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243932 2020-07-02T08:55:15 Z errorgorn Pipes (CEOI15_pipes) C++14
50 / 100
 1393 ms 18272 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.v[pa]+=dsu1.v[pb];
			dsu1.unions(pa,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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 3712 KB Output is correct
2 Incorrect 10 ms 3712 KB Wrong number of edges

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 3712 KB Output is correct
2 Correct 111 ms 3584 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 3968 KB Output is correct
2 Correct 215 ms 3968 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 332 ms 4608 KB Output is correct
2 Correct 269 ms 4984 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 428 ms 6776 KB Output is correct
2 Correct 410 ms 6776 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 662 ms 7544 KB Output is correct
2 Correct 671 ms 7328 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 902 ms 8184 KB Output is correct
2 Incorrect 895 ms 8312 KB Wrong number of edges

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1138 ms 8184 KB Output is correct
2 Incorrect 1099 ms 8312 KB Wrong number of edges

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1393 ms 7928 KB Output is correct
2 Runtime error 1348 ms 18272 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)