Submission #935164

#	Time	Username	Problem	Language	Result	Execution time	Memory
935164		MinaRagy06	Swapping Cities (APIO20_swap)	C++17	100 / 100	540 ms	57976 KiB

swap

#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long

const int N = 200'005;
int n, m;
array<int, 3> e[N];
vector<array<int, 2>> par[N], sz[N], mx[N], cnt[N];
int deg[N];
int get(vector<array<int, 2>> &v, int t) {
	int l = 0, r = v.size() - 1;
	while (l <= r) {
		int md = ((l + r) >> 1);
		if (v[md][1] <= t) {
			l = md + 1;
		} else {
			r = md - 1;
		}
	}
	return v[r][0];
}
int find(int u, int t) {
	int p = get(par[u], t);
	if (p == u) {
		return u;
	}
	return find(p, t);
}
void join(int u, int v, int t) {
	int du = ++deg[u], dv = ++deg[v];
	u = find(u, t), v = find(v, t);
	mx[u].push_back({max(mx[u].back()[0], du), t});
	mx[v].push_back({max(mx[v].back()[0], dv), t});
	cnt[u].push_back({cnt[u].back()[0] + 1, t});
	if (u == v) return;
	if (sz[u].back()[0] < sz[v].back()[0]) swap(u, v);
	par[v].push_back({u, t});
	sz[u].push_back({sz[u].back()[0] + sz[v].back()[0], t});
	cnt[u].push_back({cnt[u].back()[0] + cnt[v].back()[0], t});
	mx[u].push_back({max(mx[u].back()[0], mx[v].back()[0]), t});
}
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[i] = {u[i], v[i], w[i]};
	}
	sort(e, e + m, [&] (array<int, 3> x, array<int, 3> y) {return x[2] < y[2];});
	for (int i = 0; i < n; i++) {
		par[i].push_back({i, -1});
		sz[i].push_back({1, -1});
		mx[i].push_back({0, -1});
		cnt[i].push_back({0, -1});
		deg[i] = 0;
	}
	for (int i = 0; i < m; i++) {
		join(e[i][0], e[i][1], i);
	}
}
int getMinimumFuelCapacity(int x, int y) {
	int l = 0, r = m - 1;
	while (l <= r) {
		int md = ((l + r) >> 1);
		int p = find(x, md);
		if (p == find(y, md) && (get(mx[p], md) > 2 || get(cnt[p], md) >= get(sz[p], md))) {
			r = md - 1;
		} else {
			l = md + 1;
		}
	}
	if (l == m) {
		return -1;
	}
	return e[l][2];
}

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