oj.uz

Submission #937597

# Submission time Handle Problem Language Result Execution time Memory
937597 2024-03-04T09:31:16 Z IBory Swapping Cities (APIO20_swap) C++17
0 / 100
 1 ms 2140 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX = 200007;
int N, M, R[MAX], D[MAX];
bool T[MAX], isLine;
tuple<int, int, int> E[MAX];

void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
	N = _N, M = _M;
	for (int i = 1; i <= M; ++i) {
		E[i] = {U[i], V[i], W[i]};
		D[U[i]]++;
		D[V[i]]++;
	}
	if (_N == _M + 1 && *max_element(D, D + MAX) == 2) isLine = 1;
	sort(E + 1, E + M + 1);
}

void Clear() {
	iota(R, R + MAX, 0);
	memset(T, 0, sizeof(T));
	memset(D, 0, sizeof(D));
}

int Find(int n) {
	if (n == R[n]) return n;
	int r = Find(R[n]);
	T[r] |= T[R[n]];
	return R[n] = r;
}

void Union(int a, int b) {
	if (++D[a] == 3) T[a] = 1;
	if (++D[b] == 3) T[b] = 1;
	a = Find(a), b = Find(b);
	if (a == b) return;
	R[a] = b;
	T[b] |= T[a];
}

int getMinimumFuelCapacity(int x, int y) {
	if (isLine) return -1;

	int l = 1, r = M + 1;
	while (l + 1 < r) {
		int mid = (l + r) >> 1;

		Clear();
		for (int i = 1; i <= mid; ++i) {
			auto [_, a, b] = E[i];
			Union(a, b);
		}

		bool ok = (Find(x) == Find(y)) && T[Find(x)];
		(ok ? r : l) = mid;
	}

	auto [ans, a, b] = E[l];
	return ans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 2140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 2140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 2140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 2140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 2140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 2140 KB Output isn't correct
3 Halted 0 ms 0 KB -