oj.uz

Submission #784180

# Submission time Handle Problem Language Result Execution time Memory
784180 2023-07-15T20:38:19 Z NK_ Pipes (CEOI15_pipes) C++17
0 / 100
 2 ms 4564 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, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool sameSet(int x, int y) { return get(x) == get(y); }
	bool unite(int x, int y) {
		x = get(x), y = get(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 = [&](int u) {
	// 	ID[u] = id; 
	// 	if (PAR[u] != -1 && D.sameSet(PAR[u], u)) upd.pb(u);

	// 	for(auto &v : ADJ[u]) if (v != PAR[u]) {
	// 		PAR[v] = u, DEP[v] = DEP[u] + 1;
	// 		dfs(v);
	// 	}
	// };

	// 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
		
	// 	upd = {};

	// 	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];

	// 	return 1;
	// };


	// V<pair<int, int>> E;

	// int u, v, ui, vi;
	// 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) {
	// 			ui = D.get(u), vi = D.get(v);
				
	// 			// cout << u << " -> " << ui << endl;
	// 			// cout << v << " -> " << vi << endl;

	// 			if (ui == vi) break;
	// 			if (DEP[ui] < DEP[vi]) swap(ui, vi);
	// 			D.unite(PAR[ui], ui); // MAKE PAR[ui] the parent of ui
	// 		}
	// 	} 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 Incorrect 1 ms 212 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 1 ms 468 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Incorrect 1 ms 784 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Incorrect 1 ms 1620 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3284 KB Output is correct
2 Incorrect 2 ms 3284 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Incorrect 2 ms 3796 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4564 KB Output is correct
2 Incorrect 2 ms 4564 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4564 KB Output is correct
2 Incorrect 2 ms 4564 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Incorrect 2 ms 4564 KB Wrong number of edges
3 Halted 0 ms 0 KB -