Submission #1278656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278656		g4yuhg	Pipes (CEOI15_pipes)	C++20	100 / 100	650 ms	15192 KiB

pipes

//Huyduocdithitp
#include<bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll,ll>
#define N 100005
#define LOG 18
using namespace std;

// y tuong: vi len toi 1e6 canh, ta nhan thay chi can quan tam toi da 2 * n - 2 canh thoi. nhu the dam bao 
// tao du cac tplt manh roi
// ta se dung 2 dsu, 1 dinh duoc noi 2 lan roi thi khong can noi them nua
// toi uu: ta khong dung clear, ma dung swap() => free capacity
// vector * de khoi tao size sau

// da doc sol

const ll inf = 1e9;

bool ghuy4g;

ll n, m;
vector<ll> *adj;
ll timeDfs;
vector<ll> par, par1, num, low;

vector<pii> g;

ll find(ll u) {
	if (par[u] < 0) return u;
	return par[u] = find(par[u]);
}

void join(ll u, ll v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	if (par[u] <= par[v]) {
		par[u] += par[v];
		par[v] = u;
	}
	else {
		par[v] += par[u];
		par[u] = v;
	}
}

ll find1(ll u) {
	if (par1[u] < 0) return u;
	return par1[u] = find1(par1[u]);
}

void join1(ll u, ll v) {
	u = find1(u);
	v = find1(v);
	if (u == v) return;
	if (par1[u] <= par1[v]) {
		par1[u] += par1[v];
		par1[v] = u;
	}
	else {
		par1[v] += par1[u];
		par1[u] = v;
	}
}

void dfs(ll u, ll parent) {
	num[u] = low[u] = ++ timeDfs;
	bool see = 0;
	for (auto v : adj[u]) {
		if (v == parent && see == 0) {
			see = 1;
			continue;
		}
		if (num[v]) {
			low[u] = min(low[u], num[v]);
		}
		else {
			dfs(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] == num[v]) {
				cout << u << " " << v << endl;
			}
		}
	}
}

void solve() {
	for (int i = 1; i <= n; i ++) {
		if (num[i] == 0) {
			dfs(i, 0);
		}
	}
}

bool klinh;

signed main() {
	//freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	par.resize(n + 1, -1);
	par1.resize(n + 1, -1);
	for (int i = 1; i <= n; i ++) {
		par[i] = par1[i] = -1;
	}
	for (int i = 1; i <= m; i ++) {
		ll u, v;
		cin >> u >> v;
		if (find(u) != find(v)) {
			join(u, v);
			g.push_back({u, v});
		}
		else if (find1(u) != find1(v)) {
			join1(u, v);
			g.push_back({u, v});
		}
	}
	
	//par.clear();
	//par1.clear();
	
	vector<ll>().swap(par);     // free capacity
	vector<ll>().swap(par1);    // free capacity

	
	adj = new vector<ll> [n + 1];
	
	while (g.size()) {
		//cout << g.back().fi << " " << g.back().se << endl;
		adj[g.back().fi].push_back(g.back().se);
		adj[g.back().se].push_back(g.back().fi);
		g.pop_back();
	}
	
	vector<pii>().swap(g);      // free capacity
	
	
	num.resize(n + 1, 0);
	low.resize(n + 1, 0);
	
	solve();
	
	delete[] adj;
	
	//num.clear();
	//low.clear();
	
	vector<ll>().swap(num);
	vector<ll>().swap(low);
	
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
	
	return 0;
}

• 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