Submission #1201658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201658		A_M_Namdar	Swapping Cities (APIO20_swap)	C++20	7 / 100	130 ms	49848 KiB

swap

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

const int N = 2e5 + 10, inf = 1e9 + 100, LG = 20;
int n, m, par[N], lp[N], h[N], par2[N][LG], dp[N][LG], wei[N], h2[N];
vector<int> ver[N];
vector<pair<int, int>> adj[N];
struct EDGE {
	int u, v, w;
	friend bool operator<(EDGE p1, EDGE p2) {
		return p1.w < p2.w;
	}
};
vector<EDGE> edge;

int get_par(int u) {
	return (par[u] == -1? u: get_par(par[u]));
}

void merge(int u, int v, int w) {
	int uu = u, vv = v;
	u = get_par(u), v = get_par(v);
	if (ver[v].size() > ver[u].size()) 
		swap(u, v);
	if (u == v) {
		if (lp[u] > 1e9) 
			for (int x: ver[u]) 
				lp[x] = w;
		return;
	}
	adj[uu].push_back({vv, w});
	adj[vv].push_back({uu, w});
	if (lp[u] <= 1e9 && lp[v] > 1e9) 
		for (int x: ver[v]) 
			lp[x] = w;
	if (lp[u] > 1e9 && lp[v] <= 1e9) 
		for (int x: ver[u]) 
			lp[x] = w;
	par[v] = u;
	wei[v] = w;
	for (int x: ver[v]) 
		ver[u].push_back(x), h2[x]++;
}

void dfs(int u) {
	for (pair<int, int> e: adj[u]) 
		if (e.first != par2[u][0]) {
			par2[e.first][0] = u;
			h[e.first] = h[u] + 1;
			dfs(e.first);
		}
}

void pre() {
	sort(edge.begin(), edge.end());
	memset(par, -1, sizeof par);
	memset(par2, -1, sizeof par2);
	memset(lp, 63, sizeof lp);
	for (int i = 0; i < n; i++) 
		ver[i].push_back(i);
	for (int i = 0; i < m; i++) 
		merge(edge[i].u, edge[i].v, edge[i].w);
	dfs(0);
	for (int i = 1; i < n; i++) {
		dp[i][0] = inf;
		for (pair<int, int> e: adj[par2[i][0]]) {
			int v = e.first, w = e.second;
			if (v != i && v != par2[par2[i][0]][0]) {
				dp[i][0] = w;
				break;
			}
		}
	}
	for (int j = 1; j < LG; j++) 
		for (int i = 0; i < n; i++) 
			if (h[i] >= (1 << i)) {
				par2[i][j] = par2[par2[i][j - 1]][j - 1];
				dp[i][j] = min(dp[i][j - 1], dp[par2[i][j - 1]][j - 1]);
			}
}

void init(int nn, int mm, vector<int> u, vector<int> v, vector<int> w) {
	n = nn;
	m = mm;
	for (int i = 0; i < m; i++) 
		edge.push_back({u[i], v[i], w[i]});
	pre();
}

int lca(int u, int v, int res = 0) {
//	cout << u << ' ' << v << endl;
	if (h2[u] > h2[v]) swap(u, v);
	while (h2[v] > h2[u]) {
		res = max(res, wei[v]);
		v = par[v];
	}
	if (u == v) return res;
	while (par[u] != par[v]) {
		res = max(res, max(wei[u], wei[v]));
		u = par[u], v = par[v];
	}
	return max(res, max(wei[u], wei[v]));
}

int lca2(int u, int v, int res = inf) {
	if (h[u] > h[v]) swap(u, v);
	int cnt = 0;
	for (pair<int, int> e: adj[v]) {
		int x = e.first, w = e.second;
		if (x != par2[v][0]) 
			cnt++;
		if (cnt == 2) {
			res = min(res, w);
			break;
		}
	}
	for (int i = LG - 1; i >= 0; i--) 
		if (h[v] - (1 << i) > h[u]) {
			res = min(res, dp[v][i]);
			v = par2[v][i];
		}
	if (par2[v][0] == u) {
		cnt = 0;
		for (pair<int, int> e: adj[u]) {
			int x = e.first, w = e.second;
			if (x != v) 
				cnt++;
			if (cnt == 2) 
				return min(res, w);
		}
		return res;
	}
	if (h[v] > h[u]) {
		res = min(res, dp[v][0]);
		v = par2[v][0];
	}
	cnt = 0;
	for (pair<int, int> e: adj[u]) {
		int x = e.first, w = e.second;
		if (x != par2[u][0]) 
			cnt++;
		if (cnt == 2) {
			res =  min(res, w);
			break;
		}
	}
	for (int i = LG - 1; i >= 0; i--) 
		if (h[u] >= (1 << i) && par2[u][i] != par2[v][i]) {
			res = min(res, min(dp[u][i], dp[v][i]));
			u = par2[u][i], v = par2[v][i];
		}
	int l = par2[u][0];
	for (pair<int, int> e: adj[l]) {
		int x = e.first, w = e.second;
		if (x != v && x != u) 
			return min(res, w);
	}
//	cout << "---" << res << "---" << endl;
	return res;
}

int getMinimumFuelCapacity(int u, int v) {
	int res = lca(u, v);
//	cout << res << '\n';
	int tmp = min(max(lp[u], lp[v]), lca2(u, v));
//	cout << lp[u] << ' ' << lp[v] << ' ' << lca2(u, v) << '\n';
	if (max(res, tmp) > 1e9) return -1;
	return max(res, tmp);
}

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