oj.uz

Submission #243929

# Submission time Handle Problem Language Result Execution time Memory
243929 2020-07-02T08:52:14 Z errorgorn Pipes (CEOI15_pipes) C++14
20 / 100
 1428 ms 65536 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#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 7 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 9 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 112 ms 3712 KB Output is correct
2 Correct 117 ms 3704 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 3968 KB Output is correct
2 Correct 219 ms 3980 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 4608 KB Output is correct
2 Runtime error 278 ms 18680 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 6780 KB Output is correct
2 Runtime error 408 ms 25208 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 7288 KB Output is correct
2 Runtime error 705 ms 40752 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 914 ms 8184 KB Output is correct
2 Runtime error 971 ms 49836 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1137 ms 8228 KB Output is correct
2 Runtime error 1112 ms 61236 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1428 ms 8056 KB Output is correct
2 Runtime error 1395 ms 65536 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)