oj.uz

Submission #938179

# Submission time Handle Problem Language Result Execution time Memory
938179 2024-03-05T01:41:14 Z IBory Swapping Cities (APIO20_swap) C++17
0 / 100
 634 ms 524288 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

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

void Clear() {
	for (int i = 0; i < MAX; ++i) {
		R[i].clear();
		T[i].clear();
		C[i].clear();
		R[i].emplace_back(-1, i);
		T[i].emplace_back(-1, 0);
		C[i].emplace_back(-1, 0);
	}
	memset(D, 0, sizeof(D));
}

int Find(int n, int t) {
	int tr = R[n].back().second;
	if (T[n].back().second && !T[tr].back().second) T[tr].emplace_back(t, 1);
	if (C[n].back().second && !C[tr].back().second) C[tr].emplace_back(t, 1);
	if (n == tr) return n;
	int r = Find(tr, t);
	if (R[n].back().second != r) R[n].emplace_back(r, t);
	return R[n].back().second;
}

void Union(int a, int b, int t) {
	if (++D[a] == 3 && !T[a].back().second) T[a].emplace_back(t, 1);
	if (++D[b] == 3 && !T[b].back().second) T[b].emplace_back(t, 1);
	a = Find(a, t), b = Find(b, t);
	if (a == b) {
		if (!C[a].back().second) C[a].emplace_back(t, 1);
		return;
	}
	R[a].emplace_back(t, b);
	if (T[a].back().second && !T[b].back().second) T[b].emplace_back(t, 1);
	if (C[a].back().second && !C[b].back().second) C[b].emplace_back(t, 1);
}

int TFind(vector<pii>& S, int t) {
	auto it = upper_bound(S.begin(), S.end(), pii{t, 1 << 30});
	return (*--it).second;
}

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;
		int rx = x, ry = y;
		while (1) {
			int t = TFind(R[rx], mid);
			if (rx == t) break;
			rx = t;
		}
		while (1) {
			int t = TFind(R[ry], mid);
			if (ry == t) break;
			ry = t;
		}
		bool ok = (rx == ry && (TFind(T[rx], mid) || TFind(C[rx], mid)));
		(ok ? r : l) = mid;
	}

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

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

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 34080 KB Output is correct
2 Correct 30 ms 33880 KB Output is correct
3 Correct 27 ms 33872 KB Output is correct
4 Correct 28 ms 33872 KB Output is correct
5 Correct 28 ms 34140 KB Output is correct
6 Correct 29 ms 34044 KB Output is correct
7 Correct 29 ms 34028 KB Output is correct
8 Correct 28 ms 34136 KB Output is correct
9 Correct 80 ms 37776 KB Output is correct
10 Correct 89 ms 38600 KB Output is correct
11 Correct 88 ms 38596 KB Output is correct
12 Correct 91 ms 38864 KB Output is correct
13 Runtime error 634 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 34080 KB Output is correct
2 Correct 30 ms 33880 KB Output is correct
3 Incorrect 245 ms 42140 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 34080 KB Output is correct
2 Correct 30 ms 33880 KB Output is correct
3 Correct 27 ms 33872 KB Output is correct
4 Correct 28 ms 33872 KB Output is correct
5 Correct 28 ms 34140 KB Output is correct
6 Correct 29 ms 34044 KB Output is correct
7 Correct 29 ms 34028 KB Output is correct
8 Correct 28 ms 34136 KB Output is correct
9 Correct 28 ms 33904 KB Output is correct
10 Incorrect 27 ms 34140 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 33904 KB Output is correct
2 Correct 29 ms 34080 KB Output is correct
3 Correct 30 ms 33880 KB Output is correct
4 Correct 27 ms 33872 KB Output is correct
5 Correct 28 ms 33872 KB Output is correct
6 Correct 28 ms 34140 KB Output is correct
7 Correct 29 ms 34044 KB Output is correct
8 Correct 29 ms 34028 KB Output is correct
9 Correct 28 ms 34136 KB Output is correct
10 Correct 80 ms 37776 KB Output is correct
11 Correct 89 ms 38600 KB Output is correct
12 Correct 88 ms 38596 KB Output is correct
13 Correct 91 ms 38864 KB Output is correct
14 Runtime error 634 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 34080 KB Output is correct
2 Correct 30 ms 33880 KB Output is correct
3 Correct 27 ms 33872 KB Output is correct
4 Correct 28 ms 33872 KB Output is correct
5 Correct 28 ms 34140 KB Output is correct
6 Correct 29 ms 34044 KB Output is correct
7 Correct 29 ms 34028 KB Output is correct
8 Correct 28 ms 34136 KB Output is correct
9 Correct 80 ms 37776 KB Output is correct
10 Correct 89 ms 38600 KB Output is correct
11 Correct 88 ms 38596 KB Output is correct
12 Correct 91 ms 38864 KB Output is correct
13 Runtime error 634 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 33904 KB Output is correct
2 Correct 29 ms 34080 KB Output is correct
3 Correct 30 ms 33880 KB Output is correct
4 Correct 27 ms 33872 KB Output is correct
5 Correct 28 ms 33872 KB Output is correct
6 Correct 28 ms 34140 KB Output is correct
7 Correct 29 ms 34044 KB Output is correct
8 Correct 29 ms 34028 KB Output is correct
9 Correct 28 ms 34136 KB Output is correct
10 Correct 80 ms 37776 KB Output is correct
11 Correct 89 ms 38600 KB Output is correct
12 Correct 88 ms 38596 KB Output is correct
13 Correct 91 ms 38864 KB Output is correct
14 Runtime error 634 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -