oj.uz

답안 #858005

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
858005 2023-10-07T09:37:11 Z Faisal_Saqib Pipes (CEOI15_pipes) C++17
10 / 100
 1135 ms 17992 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 448 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 7124 KB Output is correct
2 Incorrect 158 ms 6864 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 314 ms 10068 KB Output is correct
2 Correct 293 ms 7504 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1135 ms 17992 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 456 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 4556 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 4564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -