Submission #231707

#	Time	Username	Problem	Language	Result	Execution time	Memory
231707		BamiTorabi	Pipes (CEOI15_pipes)	C++14	100 / 100	1879 ms	15328 KiB

pipes

//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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10