Submission #230128

#	Time	Username	Problem	Language	Result	Execution time	Memory
230128		Atalasion	Pipes (CEOI15_pipes)	C++14	0 / 100	1912 ms	65536 KiB

pipes

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-O2")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

int n, m, sz[2][N], par[2][N], mn[N], h[N];
vi G[N];
bool mark[N];

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

void merge(int v, int u, int id){
	int V = v, U = u;
	int vv = getpar(0, v), uu = getpar(0, u);
	if (sz[0][vv] < sz[0][uu]) swap(vv, uu);
	if (vv == uu){
		v = getpar(1, v), u = getpar(1, u);
		if (v != u){
			if (sz[1][v] < sz[1][u]) swap(v, u);
			par[1][u] = v;
			sz[1][v] += sz[1][u];
			G[V].pb(U);
			G[U].pb(V);
		//	cout << V << ' ' << U << '\n';
		}
		return;
	}
	par[0][uu] = vv;
	sz[0][vv] += sz[0][uu];
	G[u].pb(v), G[v].pb(u);
	// << v << ' ' << u << '\n';
	return;
}

void DFS(int v, int p = 0){
	mark[v] = 1;
	mn[v] = h[v];
	//cout << v << '\n';
	for (auto u:G[v]){
		if (u == p) continue;
		if (!mark[u]){
			h[u] = h[v] + 1;
			DFS(u, v);
			mn[v] = min(mn[v], mn[u]);
			if (mn[u] > h[v]){
				printf("%d %d\n", min(u, v), max(u, v));
				//int aa;
			}
		}else if(h[u] < h[v]){
			mn[v] = min(mn[v], h[u]);
		}
	}
	//cout << "Fuck " << v << ' ' << mn[v] << '\n';
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	scanf("%d %d", &n, &m);
	for (int i = 0; i < N; i++) par[0][i] = par[1][i] = i, sz[0][i] = sz[1][i] = 1; 
	for (int i = 1; i <= m; i++){
		int v, u;
		scanf("%d %d", &v, &u);
		merge(v, u, i);
	}
	for (int i = 1; i <= n; i++) if (!mark[i]) DFS(i);
	










	return 0;
}

/*
10 11
1 7
1 8
1 6
2 8
6 7
5 8
2 5
2 3
2 4
3 4
10 9
*/

Compilation message (stderr)

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

• 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