oj.uz

Submission #142668

# Submission time Handle Problem Language Result Execution time Memory
142668 2019-08-10T11:12:55 Z nots0fast Pipes (CEOI15_pipes) C++17
0 / 100
 5000 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp setprecision(12)<<fixed
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define ll int
#define double long double
#define MAX (int)(pow(10,5) + 10)
#define pb(a) push_back(a)
// #define cout out
// #define cin in
ll inf = pow(10,9);
ll modulo = pow(10,9) + 7;
double eps = 1e-10;
ifstream in;
ofstream out;


ll lca[MAX][20];
ll dep[MAX];
ll bad[MAX]; 
vector<ll> g[MAX];
vector<ll> dsu[MAX];

void pre(ll i){
	for(ll j = 1; j<20; j++)
		lca[i][j]=  lca[lca[i][j-1]][j-1];
}
 
ll LCA(ll a, ll b){
	if(dep[a] < dep[b])
		swap(a,b);
	// a is deeper now, swim a upwards
	for(ll j =19; j>-1; j--)
		if(dep[lca[a][j]] > dep[b])
			a = lca[a][j];
	if(dep[a] != dep[b])
		a = lca[a][0];
	for(ll j=19; j>-1; j--)
		if(lca[a][j]!=lca[b][j])
			a = lca[a][j], b= lca[b][j];
	if(a!=b)
		a = lca[a][0];
	return a;
}

void dfs(ll hd){
	for(auto& hr : g[hd])
		dep[hr] = dep[hd]+1, dfs(hr);
}

namespace dsu_{
	int aid[MAX];
	void ini(int n){
		fori(n)
			aid[i] = i, dsu[i].clear(), dsu[i].push_back(i), lca[i][0] = i, bad[i] = i, dep[i] = 0;
	}
	bool join(int a,int b){  //	1 - if joined, 0 - if they were already joined 
		int aid1 = aid[a], aid2 = aid[b];
		if(dsu[aid2].size() > dsu[aid1].size())
			swap(aid1,aid2);
		if(aid1==aid2)
			return 0;
		if(aid2 == aid[b])
			lca[b][0] = a, g[a].pb(b), dep[b] = dep[a]+1, dfs(b); 		// a is better , fix b
		else
			lca[a][0] = b, g[b].pb(a), dep[a] = dep[b]+1, dfs(a);		// b is better , fix a
		for(auto& hd : dsu[aid2]){
			aid[hd] = aid1;
			pre(hd);
			dsu[aid1].push_back(hd);
		}
		dsu[aid2].clear();
		return 1;
	}
};
void dfs2(ll hd){
	for(auto hr : g[hd]){
		dfs2(hr);
		if(dep[bad[hr]] < dep[bad[hd]])
			bad[hd] = bad[hr];
	}
}
void deal(){
	ll n,m;
	cin>>n>>m;
	dsu_::ini(n);
	fori(m){
		ll a, b;
		cin>>a>>b;
		--a, --b;
		if(!dsu_::join(a,b)){
			ll lc = LCA(a,b);
			if(dep[lc] < dep[bad[b]])
				bad[b] = lc;
			if(dep[lc] < dep[bad[a]])
				bad[a] = lc;
		}
//		cout<<"after "<<a<<" "<<b<<endl;
//		cout<<"parent of "<<a<<" is "<<lca[a][0]<<endl;
//		cout<<"parent of "<<b<<" is "<<lca[b][0]<<endl;	
	}
	vector<ll> roots;
	fori(n){
//		cout<<"bad for "<<i<<" is "<<bad[i]<<" parent "<<lca[i][0]<<endl;
		if(lca[i][0] != i)
			g[lca[i][0]].pb(i);
		else
			roots.pb(i);
	}
	for(auto rt : roots)
		dfs2(rt);
	fori(n){
		if(bad[i] == i && lca[i][0]!=i){
			cout<<i+1<<" "<<lca[i][0]+1<<'\n';
		}
	}
}
 
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 5880 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 11116 KB Output is correct
2 Incorrect 277 ms 10872 KB Wrong number of edges

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 9868 KB Output is correct
2 Incorrect 608 ms 9208 KB Wrong number of edges

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 919 ms 18260 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 1793 ms 32092 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 2400 ms 45664 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 3312 ms 60092 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 4231 ms 65536 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 Execution timed out 5019 ms 65536 KB Time limit exceeded
2 Halted 0 ms 0 KB -