Submission #499295

#	Time	Username	Problem	Language	Result	Execution time	Memory
499295		sidon	Swapping Cities (APIO20_swap)	C++17	6 / 100	426 ms	54296 KiB

swap

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

const int Z = 1e5, B = 18, INF = 2e9;

array<int, B> p[Z], q[Z], r[Z];
vector<int> e(Z, -1), d(Z);
vector<array<int, 2>> g[Z];
set<array<int, 2>> s[Z];

int find(int u) {
	return e[u] < 0 ? u : e[u] = find(e[u]);
}

void dfs_0(int u) {
	for(auto &[v, w] : g[u]) if(v != p[u][0]) {
		p[v][0] = u, q[v][0] = w, d[v] = d[u] + 1;
		dfs_0(v);

		if(size(s[u]) < size(s[v]))
			s[u].swap(s[v]);

		for(auto &i : s[v])
			if(s[u].find(i) == end(s[u]))
				s[u].insert(i);
			else
				s[u].erase(i);
	}
	if(!empty(s[u])) r[u][0] = (*begin(s[u]))[0];
	else r[u][0] = INF;
}

void dfs_1(int u) {
	for(int i = 1; i < B; i++) {
		p[u][i] = p[p[u][i-1]][i-1];
		q[u][i] = max(q[u][i-1], q[p[u][i-1]][i-1]);
		r[u][i] = min(r[u][i-1], r[p[u][i-1]][i-1]);
	}
	for(auto &[v, w] : g[u]) if(v != p[u][0])
		dfs_1(v);
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	array<int, 3> h[M];
	for(int i = 0; i < M; i++) {
		h[i] = {W[i], U[i], V[i]};
	}
	sort(h, h+M);
	for(int i = 0; i < M; i++) {
		int u = find(h[i][1]), v = find(h[i][2]), w = h[i][0];
		if(u == v)
			for(int k : {1, 2})
				s[h[i][k]].insert({w, i});
		else {
			if(e[u] > e[v]) swap(u, v);
			e[u] += e[v], e[v] = u;
			for(int k : {1, 2})
				g[h[i][k]].push_back({h[i][3-k], w});
		}
	}

	for(int &i : r[0]) i = INF;

	dfs_0(0), dfs_1(0);
}

int getMinimumFuelCapacity(int X, int Y) {
	int u = X, v = Y, qV = 0, rV = INF;

	if(d[u] > d[v]) swap(u, v);
	for(int i = 0; i < B; i++) {
		if((d[v] - d[u]) & (1<<i)) {
			qV = max(qV, q[v][i]);
			rV = min(rV, r[v][i]);
			v = p[v][i];
		}
	}
	if(u != v) {	
		for(int i = B; --i; ) {
			if(p[u][i] != p[v][i]) {
				qV = max({qV, q[u][i], q[v][i]});
				rV = min({rV, r[u][i], r[v][i]});
				u = p[u][i];
				v = p[v][i];
			}
		}
		qV = max({qV, q[u][0], q[v][0]});
		rV = min({rV, r[u][0], r[v][0]});
	}
	return rV == INF ? -1 : max(rV, qV);
}

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