oj.uz

Submission #857843

# Submission time Handle Problem Language Result Execution time Memory
857843 2023-10-07T05:19:09 Z Faisal_Saqib Pipes (CEOI15_pipes) C++17
30 / 100
 303 ms 22608 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 856 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1624 KB Output is correct
2 Correct 6 ms 1372 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 14624 KB Output is correct
2 Correct 131 ms 13656 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 303 ms 22608 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1368 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -