Submission #857843

#	Time	Username	Problem	Language	Result	Execution time	Memory
857843		Faisal_Saqib	Pipes (CEOI15_pipes)	C++17	30 / 100	303 ms	22608 KiB

pipes

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
using namespace std;
const int MAXN=10000+10;
const int LGN=15;
int h[MAXN];
bitset<MAXN> vis;
vector<int> ma[MAXN];
int par[MAXN][LGN];
int AffectedUpTil[MAXN];
void dfs_for_lca(int& x,int& p)
{
	vis[x]=1;
	h[x]=h[p]+1;
	par[x][0]=p;
	for(int j=1;j<LGN;j++)
	{
		par[x][j]=par[par[x][j-1]][j-1];
	}
	for(auto y:ma[x])
	{
		if(!vis[y])
		{
			dfs_for_lca(y,x);
		}
	}
}
int lca(int a,int b)
{
	if(h[a]>h[b])
		swap(a,b);
	int dist=h[b]-h[a];
	while(dist)
	{
		b=par[b][(int)log2(dist&(-dist))];
		dist-=(dist&-dist);
	}
	if(a==b)
	{
		return a;
	}
	for(int i=LGN-1;i>=0;i--)
	{
		if(par[a][i]!=par[b][i])
		{
			a=par[a][i];
			b=par[b][i];
		}
	}
	return par[a][0];
}

void dfs_tree(int& x,int& p)
{
	vis[x]=1;
	for(auto y:ma[x])
	{
		if(!vis[y])
		{
			dfs_tree(y,x);
		}
		else if(y!=p)
		{
			int a=x;
			int b=y;
			int c=lca(a,b);
			if(h[AffectedUpTil[a]]>h[c])
			{
				AffectedUpTil[a]=c;
			}
			if(h[AffectedUpTil[b]]>h[c])
			{
				AffectedUpTil[b]=c;
			}
		}
	}
}
void dfs_ans(int& x)
{
	vis[x]=1;
	for(auto y:ma[x])
	{
		if(!vis[y])
		{
			dfs_ans(y);
			if(AffectedUpTil[y]==y)
			{
				cout<<x<<' '<<y<<'\n';
			}
			if(h[AffectedUpTil[x]]>h[AffectedUpTil[y]])
			{
				AffectedUpTil[x]=AffectedUpTil[y];
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
  int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		ma[x].push_back(y);
		ma[y].push_back(x);
	}
	int cp=0;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			dfs_for_lca(i,cp);
		}
	}
	for(int i=1;i<=n;i++)
	{
		vis[i]=0;
	}
	for(int i=1;i<=n;i++)
	{
		AffectedUpTil[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			dfs_tree(i,cp);
		}
	}
	for(int i=1;i<=n;i++)
	{
		vis[i]=0;
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			dfs_ans(i);
		}
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 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