Submission #642554

#	Time	Username	Problem	Language	Result	Execution time	Memory
642554		ymm	Swapping Cities (APIO20_swap)	C++17	6 / 100	166 ms	32732 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200010;
const int inf = 2e9;
const int lg = 18;
int par[N];
int sz[N];
int tim[N];
int lca[N][lg];
int lcaw[N][lg];
vector<int> A[N];

int root (int v) { return par[v] == -1? v: root(par[v]); }
void unite(int v, int u, int w)
{
	v = root(v);
	u = root(u);
	if (v == u) {
		tim[v] = min(tim[v], w);
		return;
	}
	if (sz[v] < sz[u])
		swap(v, u);
	par[u] = v;
	lcaw[u][0] = w;
	A[v].push_back(u);
	sz[v] += sz[u];
	if (tim[u] != inf)
		tim[v] = min(tim[v], w);
}

void dfs(int v, int p, int w)
{
	w = tim[v] = min(tim[v], w);
	lca[v][0] = p;
	Loop (i,0,lg-1) {
		lca[v][i+1] = lca[lca[v][i]][i];
		lcaw[v][i+1] = max(lcaw[v][i], lcaw[lca[v][i]][i]);
	}
	for (int u : A[v])
		if (u != p)
			dfs(u, v, w);
}

void init(int n, int m,
          std::vector<int> u, std::vector<int> v, std::vector<int> w) {
	vector<pair<int,pii>> vec;
	Loop (i,0,m)
		vec.push_back({w[i],{v[i],u[i]}});
	fill(par, par+N, -1);
	fill(sz, sz+N, 1);
	fill(tim, tim+N, inf);
	sort(vec.begin(), vec.end());
	for (auto dard : vec)
		unite(dard.second.first, dard.second.second, dard.first);
	int rt = 0;
	while (par[rt] != -1)
		++rt;
	dfs(rt, rt, inf);
}

int getMinimumFuelCapacity(int x, int y) {
	int w = 0;
	LoopR (i,0,lg) {
		if (lca[x][i] != lca[y][i]) {
			w = max(w, lcaw[x][i]);
			w = max(w, lcaw[y][i]);
			x = lca[x][i];
			y = lca[y][i];
		}
	}
	w = max(w, lcaw[x][0]);
	w = max(w, lcaw[y][0]);
	x = lca[x][0];
	w = max(w, tim[x]);
	return w == inf? -1: w;
}

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