oj.uz

Submission #116689

# Submission time Handle Problem Language Result Execution time Memory
116689 2019-06-13T14:47:38 Z fleimgruber Pipes (CEOI15_pipes) C++17
60 / 100
 1543 ms 51028 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);
	int cnt = 0;
	while (m--)
	{
		scanf("%d %d",&a,&b);
		if (d1.connect(a,b) || d2.connect(a,b))
		{
			cnt++;
			assert(cnt < 2*n);
			e[a].push_back(b);
			e[b].push_back(a);
		}
	}
	bridges();
	return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:76: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:81: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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3200 KB Output is correct
2 Correct 8 ms 2944 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 3088 KB Output is correct
2 Correct 118 ms 2916 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 3832 KB Output is correct
2 Correct 249 ms 3320 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 5496 KB Output is correct
2 Correct 294 ms 5252 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 10876 KB Output is correct
2 Correct 451 ms 7544 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 783 ms 12072 KB Output is correct
2 Runtime error 726 ms 42920 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1062 ms 14288 KB Output is correct
2 Runtime error 1114 ms 51028 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1280 ms 19156 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

# Verdict Execution time Memory Grader output
1 Runtime error 1543 ms 31196 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -