Submission #858005

#	Time	Username	Problem	Language	Result	Execution time	Memory
858005		Faisal_Saqib	Pipes (CEOI15_pipes)	C++17	10 / 100	1135 ms	17992 KiB

pipes

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
using namespace std;
const int MAXN=10000+10;
int h[MAXN];
int n;
bitset<MAXN> vis;
bitset<MAXN> ma[MAXN];
int AffectedUpTil[MAXN];
void dfs_for_lca(int& x,int& p)
{
	vis[x]=1;
	h[x]=h[p]+1;
	for(int y=1;y<=n;y++)
	{
		if(!vis[y] and ma[x][y])
		{
			dfs_for_lca(y,x);
		}
	}
}
void dfs_tree(int& x,int& p)
{
	vis[x]=1;
	for(int y=1;y<=n;y++)
	{
		if(!ma[x][y])
		{
			continue;
		}
		if(!vis[y])
		{
			dfs_tree(y,x);
		}
		else if(y!=p)
		{
			int a=x;
			int b=y;
			int c=1;
			if(h[a]<=h[b])
			{
				c=a;
			}
			else
			{
				c=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(int y=1;y<=n;y++)
	{
		if(!ma[x][y])
		{
			continue;
		}
		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()
{
	int m;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		ma[x][y]=1;
		ma[y][x]=1;
	}
	int cp=0;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			dfs_for_lca(i,cp);
		}
	}
	vis.reset();
	for(int i=1;i<=n;i++)
	{
		AffectedUpTil[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			dfs_tree(i,cp);
		}
	}
	vis.reset();
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			dfs_ans(i);
		}
	}
	return 0;
}

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