oj.uz

답안 #116688

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116688 2019-06-13T14:34:18 Z fleimgruber Pipes (CEOI15_pipes) C++17
40 / 100
 1599 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;

//bridge finding
int n,t,in[MAX_N];
vector<int> e[MAX_N];

int dfs(int i, int p = -1)
{
	in[i] = ++t;
	int lo = in[i];
	for (int g : e[i])
	{
		if (g == p)
		{
			p = -1;
			continue;
		}
		if (in[g])
			lo = min(lo,in[g]);
		else
		{
			int lg = dfs(g,i);
			if (lg > in[i])
				printf("%d %d\n",i,g);
			lo = min(lo,lg);
		}
	}
	return lo;
}

void bridges()
{
	for (int i=1; i<=n; i++)
		if (!in[i])
			dfs(i);
}
//-----
struct
{
	int p[MAX_N],s[MAX_N];

	void init(int n)
	{
		for (int i=1; i<=n; i++)
			p[i] = i, s[i] = 1;
	}

	int f(int i)
	{
		if (p[i] == i)
			return i;
		return p[i]=f(p[i]);
	}
	
	bool connect(int a, int b)
	{
		a = f(a), b = f(b);
		if (a == b)
			return false;
		if (s[a] > s[b])
			swap(a,b);
		p[a] = b;
		s[b] += s[a];
		return true;
	}
} d1,d2;

int main()
{
	int m,a,b;
	scanf("%d %d",&n,&m);
	d1.init(n), d2.init(n);
	while (m--)
	{
		scanf("%d %d",&a,&b);
		if (d1.connect(a,b) || d2.connect(a,b))
		{
			e[a].push_back(b);
			e[b].push_back(a);
		}
	}
	bridges();
	return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
pipes.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 3200 KB Output is correct
2 Correct 9 ms 2944 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 3088 KB Output is correct
2 Correct 116 ms 2944 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 3784 KB Output is correct
2 Correct 233 ms 14644 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 347 ms 5496 KB Output is correct
2 Runtime error 303 ms 19164 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 478 ms 11068 KB Output is correct
2 Runtime error 505 ms 25720 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 771 ms 32800 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1090 ms 58480 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1332 ms 65536 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1599 ms 65536 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -