Submission #535992

#	Time	Username	Problem	Language	Result	Execution time	Memory
535992		lunchbox	Swapping Cities (APIO20_swap)	C++17	6 / 100	117 ms	6976 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
using namespace std;

#define N	100000
#define INF	0x3f3f3f3f

int ds[N], ww1[N], ww2[N];

int find(int i) {
	return ds[i] < 0 ? i : find(ds[i]);
}

void join(int i, int j, int w) {
	i = find(i), j = find(j);
	if (i == j)
		ww2[i] = min(ww2[i], w);
	else {
		if (ds[i] > ds[j])
			swap(i, j);
		ds[i] += ds[j], ds[j] = i;
		ww1[j] = w;
		ww2[i] = min(ww2[i], ww2[j]);
	}
}

void init(int n, int m, std::vector<int> ii, std::vector<int> jj, std::vector<int> ww) {
	vector<int> hh(m);
	for (int i = 0; i < m; i++)
		hh[i] = i;
	sort(hh.begin(), hh.end(), [&](int i, int j) {
		return ww[i] < ww[j];
	});
	memset(ds, -1, n * sizeof *ds);
	memset(ww1, 0x3f, n * sizeof *ww1);
	memset(ww2, 0x3f, n * sizeof *ww2);
	for (int h : hh)
		join(ii[h], jj[h], ww[h]);
}

int getMinimumFuelCapacity(int i, int j) {
	int w1 = -1;

	while (i != j && (ds[i] >= 0 || ds[j] >= 0)) {
		if (ww1[i] < ww1[j]) {
			w1 = ww1[i];
			i = ds[i];
		} else {
			w1 = ww1[j];
			j = ds[j];
		}
	}
	while (i >= 0) {
		if (ww2[i] != INF)
			return max(w1, ww2[i]);
		w1 = ww1[i];
		i = ds[i];
	}
	return -1;
}

/*
int main() {
	int _N, _M;
	cin >> _N >> _M;
	vector<int> _U(_M), _V(_M), _W(_M);
	for (int i = 0; i < _M; i++)
		cin >> _U[i] >> _V[i] >> _W[i];
	init(_N, _M, _U, _V, _W);

	int _Q;
	cin >> _Q;
	while (_Q--) {
		int _u, _v;
		cin >> _u >> _v;
		cout << getMinimumFuelCapacity(_u, _v) << '\n';
	}
}
*/

• Subtask 1: 6 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27