Submission #142668

#	Time	Username	Problem	Language	Result	Execution time	Memory
142668		nots0fast	Pipes (CEOI15_pipes)	C++17	0 / 100	5019 ms	65536 KiB

pipes

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10