oj.uz

Submission #243927

# Submission time Handle Problem Language Result Execution time Memory
243927 2020-07-02T08:42:11 Z errorgorn Pipes (CEOI15_pipes) C++14
40 / 100
 1514 ms 46724 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];
	
	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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3968 KB Output is correct
2 Correct 12 ms 4096 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 9312 KB Output is correct
2 Correct 104 ms 9208 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 13944 KB Output is correct
2 Correct 236 ms 15864 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 332 ms 21808 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 503 ms 28924 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 Runtime error 772 ms 44536 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1067 ms 20088 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 1249 ms 34168 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 1514 ms 46724 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -