Submission #231696

#	Time	Username	Problem	Language	Result	Execution time	Memory
231696		BamiTorabi	Pipes (CEOI15_pipes)	C++14	0 / 100	1905 ms	52240 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];
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 (stderr)

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