oj.uz

Submission #546457

# Submission time Handle Problem Language Result Execution time Memory
546457 2022-04-07T15:40:24 Z blue Pipes (CEOI15_pipes) C++17
0 / 100
 892 ms 7160 KB 
#include <iostream>
#include <vector>
using namespace std;

const int mx = 100'000;


int N, M;

struct disjoint_set
{
	int parent[1+mx];
	int subtree[1+mx];

	disjoint_set()
	{
		for(int i = 1; i <= mx; i++)
		{
			parent[i] = i;
			subtree[i] = 1;
		}
	}

	int root(int u)
	{
		if(parent[u] == u) return u;
		else return (parent[u] = root(parent[u]));
	}

	bool join(int u, int v)
	{
		u = root(u);
		v = root(v);
		if(u == v) return 0;

		if(subtree[u] < subtree[v]) swap(u, v);
		parent[v] = u;
		subtree[u] += subtree[v];

		return 1;
	}
};

int lowlink[1+mx];

int dfsind[1+mx];

int dfscurr;

int paredge[1+mx];

int degree[1+mx];

int* edgelist[1+mx];

int eu[2*mx + 1], ev[2*mx + 1];


void dfs(int u)
{
	// cerr << "dfs " << u << '\n';
	// cerr << "paredge = ";
	// for(int i = 1; i <= N; i++) cerr << paredge[i] << ' ';
		// cerr << '\n';
	dfsind[u] = ++dfscurr;

	for(int h = 0; h < degree[u]; h++)
	{
		int e = edgelist[u][h];
		if(e == paredge[u]) continue;

		int v = eu[e] + ev[e] - u;

		if(dfsind[v] == 0)
		{
			// cerr << "edge " << u << " -> " << v << '\n';
			paredge[v] = e;
			dfs(v);
			lowlink[u] = min(lowlink[u], lowlink[v]);
		}
		else
		{
			lowlink[u] = min(lowlink[u], dfsind[v]);
		}
	}

	// cerr << "dfs end " << u << " : " << lowlink[u] << ' ' << dfsind[u] << '\n';
	// cerr << "paredge = ";
	// for(int i = 1; i <= N; i++) cerr << paredge[i] << ' ';
	// 	cerr << '\n';

	if(lowlink[u] >= dfsind[u] && paredge[u] != 0)
	{
		// cerr << "\n\n";
		// cerr << "paredge " << u << " = " << paredge[u] << '\n';
		// cerr << "bridge detected : ";
		cout << eu[paredge[u]] << ' ' << ev[paredge[u]] << '\n';
		// cerr << "\n\n";
	}
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;

	disjoint_set A;
	disjoint_set B;

	int ect = 0;



	for(int e = 1; e <= M; e++)
	{
		int u, v;
		cin >> u >> v;

		if(A.join(u, v))
		{
			ect++;
			eu[ect] = u;
			ev[ect] = v;
		}
		else if(B.join(u, v))
		{
			ect++;
			eu[ect] = u;
			ev[ect] = v;
		}
	}

	delete A.parent;
	delete A.subtree;
	delete B.parent;
	delete B.subtree;

	for(int i = 1; i <= N; i++) degree[i] = 0;

	for(int e = 1; e <= ect; e++)
	{
		degree[eu[e]]++;
		degree[ev[e]]++;
	}

	for(int i = 1; i <= N; i++)
	{
		edgelist[i] = new int[degree[i]];
	}


	int currind[1+N];
	for(int i = 1; i <= N; i++) currind[i] = -1;

	// cerr << "done\n";

	for(int e = 1; e <= ect; e++)
	{
		currind[eu[e]]++;
		currind[ev[e]]++;

		// cerr << currind[eu[e]] << ' ' << degree[eu[e]] << '\n';
		// cerr << currind[ev[e]] << ' ' << degree[ev[e]] << '\n';

		edgelist[eu[e]][currind[eu[e]]] = e;
		edgelist[ev[e]][currind[ev[e]]] = e;
	}

// cerr << "\n\n\n\n";

	for(int i = 1; i <= N; i++) 
	{
		lowlink[i] = 1'000'000;
		dfsind[i] = 0;
		paredge[i] = 0;
	}

	dfscurr = 0;

	for(int i = 1; i <= N; i++)
	{
		if(dfsind[i]) continue;

		dfs(i);
	}
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:136:11: warning: deleting array 'A.disjoint_set::parent'
  136 |  delete A.parent;
      |         ~~^~~~~~
pipes.cpp:137:11: warning: deleting array 'A.disjoint_set::subtree'
  137 |  delete A.subtree;
      |         ~~^~~~~~~
pipes.cpp:138:11: warning: deleting array 'B.disjoint_set::parent'
  138 |  delete B.parent;
      |         ~~^~~~~~
pipes.cpp:139:11: warning: deleting array 'B.disjoint_set::subtree'
  139 |  delete B.subtree;
      |         ~~^~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 3668 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 3828 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 81 ms 3940 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 132 ms 4148 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 243 ms 4504 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 287 ms 6084 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 448 ms 6536 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 585 ms 7116 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 706 ms 7160 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 892 ms 6872 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -