oj.uz

Submission #231707

# Submission time Handle Problem Language Result Execution time Memory
231707 2020-05-14T13:28:22 Z BamiTorabi Pipes (CEOI15_pipes) C++14
100 / 100
 1879 ms 15328 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 = H[v];
	bool flag = false;
	for (int u : G[v]){
		if (mark[u]){
			if (u == p && !flag){
				flag = true;
				continue;
			}
			arumin = min(arumin, H[u]);
		}
		else
			arumin = min(arumin, DFS(u, v));
	}
	if (p && 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 (i == getpar(0, 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:74: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:76: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3968 KB Output is correct
2 Correct 13 ms 3840 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 3832 KB Output is correct
2 Correct 153 ms 3704 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 4476 KB Output is correct
2 Correct 331 ms 15328 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 5752 KB Output is correct
2 Correct 377 ms 5368 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 10056 KB Output is correct
2 Correct 546 ms 7460 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 11000 KB Output is correct
2 Correct 908 ms 8696 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1232 ms 12792 KB Output is correct
2 Correct 1168 ms 9076 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1540 ms 12844 KB Output is correct
2 Correct 1451 ms 8928 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1879 ms 12312 KB Output is correct
2 Correct 1754 ms 9848 KB Output is correct