Submission #292122

#	Time	Username	Problem	Language	Result	Execution time	Memory
292122		srvlt	Swapping Cities (APIO20_swap)	C++14	100 / 100	428 ms	36872 KiB

swap

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include "swap.h"

const int n0 = 2e5 + 123;
int n, m, ans[n0], deg[n0], inf;
vector <array <int, 3>> e;
vector <int> dsu[n0];
vector <array <int, 2>> p[n0];

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N, m = M;
	for (int i = 0; i < m; i++)
		e.pb({W[i], U[i], V[i]});
	sort(all(e));
	memset(& ans, 0x3f, sizeof(ans));
	inf = ans[0];
	for (int i = 0; i < n; i++)
		p[i].pb({0, i}), dsu[i].pb(i);
	for (auto i : e) {
		int w = i[0], u = i[1], v = i[2];
		int vc = p[v].back()[1], uc = p[u].back()[1];
		if (vc == uc)
			ans[vc] = min(ans[vc], w);
		else {
			if (SZ(dsu[vc]) < SZ(dsu[uc])) {
				swap(vc, uc);
				swap(v, u);
			}
			deg[v]++, deg[u]++;
			ans[vc] = min(ans[vc], max(w, ans[uc]));
			if (deg[v] > 2 || deg[u] > 2)
				ans[vc] = min(ans[vc], w);
			for (int x : dsu[uc]) {
				dsu[vc].pb(x);
				p[x].pb({w, vc});
			}
		}
	}
}

int getMinimumFuelCapacity(int x, int y) {
	int i = SZ(p[x]) - 1, j = SZ(p[y]) - 1, mt = inf;
	while (i >= 0 && j >= 0 && p[x][i][1] == p[y][j][1]) {
		mt = min(mt, max({ans[p[x][i][1]], p[x][i][0], p[y][j][0]}));
		i--, j--;
	}
	return (mt == inf) ? -1 : mt;
}

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