oj.uz

Submission #231701

# Submission time Handle Problem Language Result Execution time Memory
231701 2020-05-14T13:16:22 Z BamiTorabi Pipes (CEOI15_pipes) C++14
0 / 100
 1815 ms 34468 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];
vector <int> G[maxN];

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;
}

int DFS(int v, int p = 0){
	H[v] = H[p] + 1;
	mark[v] = true;
	int arumin = 0;
	for (int u : G[v]){
		if (mark[u]){
			if (u == p)
				continue;
			if (arumin == 0 || H[arumin] > H[u])
				arumin = u;
		}
		else{
			int erwin = DFS(u, v);
			if (arumin == 0 || H[arumin] > H[erwin])
				arumin = erwin;
		}
	}
	if (p && (arumin == 0 || H[arumin] >= H[v]))
		printf("%d %d\n", p, v);
	return arumin;
}

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);
	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:75: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:77: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 8 ms 3456 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 5716 KB Output is correct
2 Incorrect 177 ms 5584 KB Wrong number of edges

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 956 ms 12200 KB Output is correct
2 Runtime error 886 ms 19868 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 1216 ms 13944 KB Output is correct
2 Runtime error 1148 ms 23672 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 Correct 1468 ms 12024 KB Output is correct
2 Runtime error 1459 ms 18552 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #10
0 / 10.0

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