Submission #718493

#	Time	Username	Problem	Language	Result	Execution time	Memory
718493		Radin_Zahedi2	Swapping Cities (APIO20_swap)	C++17	100 / 100	199 ms	32072 KiB

swap

#include<bits/stdc++.h>
#include "swap.h"
//#include <vector>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int inf = 1e9 + 1;


const int N = 1e5;
const int L = 17;
int par[N];
vector<int> have[N];
int endps[N][2];

int path[N];

int edge[N];
int ind[N];
int sprc[L][N];

void cresprc(vector<int> &v) {
	int n = sz(v);

	for (int ind = 0; ind < n; ind++) {
		sprc[0][ind] = edge[v[ind]];
	}

	for (int lvl = 1; lvl < L; lvl++) {
		int len = (1 << lvl);

		for (int i = 0; n - i >= len; i++) {
			sprc[lvl][i] = max(sprc[lvl - 1][i], sprc[lvl - 1][i + (len >> 1)]);
		}
	}
}

int dist(int x, int y) {
	if (x == y) {
		return 0;
	}

	if (ind[x] > ind[y]) {
		swap(x, y);
	}

	x = ind[x] + 1;
	y = ind[y];

	int len = y - x + 1;
	int lg = __lg(len);

	return max(sprc[lg][x], sprc[lg][y - (1 << lg) + 1]);
}

void unio(int u, int v, int w) {
	int p1 = par[u], p2 = par[v];
	if (p1 == p2) {
		if (endps[p1][0] != -1) {
			endps[p1][0] = -1;
			endps[p1][1] = -1;
			for (auto x : have[p1]) {
				path[x] = w;
			}
		}
		return;
	}

	if (sz(have[p1]) < sz(have[p2])) {
		swap(p1, p2);
		swap(u, v);
	}


	bool ipath = true;
	if (endps[p1][0] == -1 || endps[p1][1] == -1 || endps[p2][0] == -1 || endps[p2][1] == -1) {
		ipath = false;
	}
	else {
		ipath = false;
		for (int x = 0; x < 2; x++) {
			for (int y = 0; y < 2; y++) {
				if (endps[p1][x] == u && endps[p2][y] == v) {
					int e1 = endps[p1][!x];
					int e2 = endps[p2][!y];
					endps[p1][0] = e1;
					endps[p1][1] = e2;

					ipath = true;
					break;
				}
			}
			if (ipath) {
				break;
			}
		}
	}

	if (!ipath && endps[p1][0] != -1) {
		for (auto x : have[p1]) {
			path[x] = w;
		}
		endps[p1][0] = -1;
		endps[p1][1] = -1;
	}
	if (!ipath && endps[p2][0] != -1) {
		for (auto x : have[p2]) {
			path[x] = w;
		}
		endps[p2][0] = -1;
		endps[p2][1] = -1;
	}


	edge[have[p2][0]] = w;
	for (auto x : have[p2]) {
		have[p1].pb(x);
		par[x] = p1;
	}
	have[p2].clear();
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {

	pair<int, int> edges[M];
	for (int e = 0; e < M; e++) {
		edges[e] = mp(W[e], e);
	}
	sort(edges + 0, edges + M);

	

	for (int v = 0; v < N; v++) {
		par[v] = v;
		have[v].pb(v);
		endps[v][0] = v;
		endps[v][1] = v;
	}


	for (int eind = 0; eind < M; eind++) {
		int e = edges[eind].se;
		int u = U[e];
		int v = V[e];
		int w = W[e];

		unio(u, v, w);
	}

	for (int v = 0; v < N - 1; v++) {
		unio(v, v + 1, inf);
	}

	for (int v = 0; v < N; v++) {
		if (!path[v]) {
			path[v] = inf;
		}
	}


	int p = par[0];
	for (int i = 0; i < N; i++) {
		ind[have[p][i]] = i;
	}

	cresprc(have[p]);
}

int getMinimumFuelCapacity(int X, int Y) {
	int ans = max(dist(X, Y), max(path[X], path[Y]));

	if (ans == inf) {
		return -1;
	}
	return ans;
}

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