oj.uz

Submission #784210

# Submission time Handle Problem Language Result Execution time Memory
784210 2023-07-15T21:03:29 Z NK_ Pipes (CEOI15_pipes) C++17
0 / 100
 5000 ms 7244 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define f first
#define s second
#define mp make_pair
#define pb push_back
 
using pi = pair<int, int>;
template<class T> using V = vector<T>;
 
struct DSU {
	V<int> e; void init(int N) { e = V<int>(N); iota(begin(e), end(e), 0); }
	void get(const int &x) { 
		if (e[x] == x) return;
		e[x] = e[e[x]];
	}
	bool sameSet(int x, int y) { get(x); get(y); return e[x] == e[y]; }
	bool unite(int x, int y) {
		get(x); get(y); x = e[x], y = e[y]; 
		if (x == y) return 0;
		e[y] = x; return 1;
	}
};
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; cin >> N >> M;

	V<V<int>> ADJ(N);
	V<int> ID(N), SIZ(N), PAR(N), DEP(N);
	DSU D; D.init(N); // for BCC
 
	// ID and SIZ are part of the DSU
	// while ADJ, PAR, DEP, and S store info about all the nodes 
	// of the spanning "tree" in its current state (AKA not necessarily connected and subject to change)
 
	for(int i = 0; i < N; i++) {
		ID[i] = i, SIZ[i] = 1;
		PAR[i] = -1;
		ADJ[i] = {};
	}
 
	int id = -1;
	V<int> upd;
 
	function<void(int)> dfs = [&](const int &u) {
		if (PAR[u] != -1 && D.sameSet(PAR[u], u)) upd.pb(u);
 
		for(auto &v : ADJ[u]) if (v != PAR[u]) {
			assert(ID[v] == ID[u]);
			PAR[v] = u, DEP[v] = DEP[u] + 1;
			dfs(v);
		}
 
		ID[u] = id; 
	};
 
	int xi, yi;
	auto merge = [&](int x, int y) {
		xi = ID[x], yi = ID[y]; if (xi == yi) return 0;
 
		if (SIZ[xi] < SIZ[yi]) swap(xi, yi), swap(x, y);
 
		// cout << xi << " " << yi << endl;
		// yi is the smaller one
		SIZ[xi] += SIZ[yi];
 
		// RECOMPUTE PARENTS FOR yi AND CHANGE ID TO xi FOR EACH NODE
		// ADD EDGE BETWEEN x AND y
		
		PAR[y] = x;
		DEP[y] = DEP[x] + 1;
		id = xi; 
 
		dfs(y);
 
		ADJ[x].pb(y); ADJ[y].pb(x);
 
		for(auto &u : upd) D.e[u] = PAR[u];
		upd = {};
 
		return 1;
	};
 
 
	V<pair<int, int>> E;
 
	int u, v;
	for(int e = 0; e < M; e++) {
		cin >> u >> v; --u, --v;
 
		if (!merge(u, v)) { // if not part of the spanning "tree"
			while(1) {
				D.get(u); D.get(v);
				
				// cout << u << " -> " << D.e[u] << endl;
				// cout << v << " -> " << D.e[v] << endl;
 
				if (D.e[u] == D.e[v]) break;
				if (DEP[D.e[u]] > DEP[D.e[v]]) D.unite(PAR[D.e[u]], D.e[u]);
				else D.unite(PAR[D.e[v]], D.e[v]);
			}
		} else { // part of spanning "tree" (possible bridge)
			// cout << "ST: " << u << " <-> " << v << endl;
			E.pb({u, v});
		}
	}
 
	for(auto& e : E) if (!D.sameSet(e.f, e.s)) {
		cout << e.f + 1 << " " << e.s + 1 << endl;
	}
 
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5044 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5045 ms 596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5057 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5049 ms 980 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5045 ms 1876 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5062 ms 5072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5039 ms 5712 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5037 ms 7236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5072 ms 7244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5039 ms 7068 KB Time limit exceeded
2 Halted 0 ms 0 KB -