oj.uz

Submission #231696

# Submission time Handle Problem Language Result Execution time Memory
231696 2020-05-14T13:09:17 Z BamiTorabi Pipes (CEOI15_pipes) C++14
0 / 100
 1905 ms 52240 KB 
//Sasayego! Sasayego! Shinzou wo Sasageyo!

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 1e5 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

bool mark[maxN];
int par[2][maxN], H[maxN];
int arumin[maxN];
vector <int> G[maxN];
vector <pii> vec;

int getpar(int b, int v){
	return (par[b][v] == v ? v : par[b][v] = getpar(b, par[b][v]));
}

bool join(int b, int u, int v){
	int pu = getpar(b, u);
	int pv = getpar(b, v);
	if (pu == pv)
		return false;
	par[b][pu] = pv;
	G[v].push_back(u);
	G[u].push_back(v);
	return true;
}

void DFS(int v, int p = 0){
	H[v] = H[p] + 1;
	mark[v] = true;
	for (int u : G[v]){
		if (mark[u]){
			if (u == p)
				continue;
			if (arumin[v] == 0 || H[arumin[v]] > H[u])
				arumin[v] = u;
		}
		else{
			DFS(u, v);
			if (arumin[v] == 0 || H[arumin[v]] > H[arumin[u]])
				arumin[v] = arumin[u];
		}
	}
	if (p && H[arumin[v]] >= H[v])
		vec.push_back({p, v});
	return;
}

int main(){
	time_t START = clock();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	iota(par[0], par[0] + maxN, 0);
	iota(par[1], par[1] + maxN, 0);
	int n, m; scanf("%d%d", &n, &m);
	while (m--){
		int u, v; scanf("%d%d", &u, &v);
		if (!join(0, u, v))
			join(1, u, v);
	}
	for (int i = 1; i <= n; i++)
		if (!mark[i])
			DFS(i);
	for (auto pp : vec)
		printf("%d %d\n", pp.first, pp.second);
	time_t FINISH = clock();
	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
	return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:76:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m; scanf("%d%d", &n, &m);
            ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d%d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3328 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 4096 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 9336 KB Output is correct
2 Incorrect 161 ms 9080 KB Wrong number of edges

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 280 ms 14072 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

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

# Verdict Execution time Memory Grader output
1 Runtime error 1593 ms 39352 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 1905 ms 52240 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -