Submission #1288609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288609		Jawad_Akbar_JJ	Swapping Cities (APIO20_swap)	C++20	30 / 100	116 ms	42532 KiB

swap

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1<<18;
vector<pair<int,int>> nei[N], nei2[N], Ed;
int Edge[N], Edg[N], Par[N], stp[N][20], Mx[N][20], hei[N], MinTrg[N], seen[N], Sz[N], inf = 1e9 + 7;

void dfs(int u, int p, int id){
	seen[u] = 1;
	hei[u] = hei[p] + 1;
	MinTrg[u] = inf;

	Mx[u][0] = Edg[id];
	for (int i=0;i<17;i++){
		Mx[u][i+1] = max(Mx[u][i], Mx[stp[u][i]][i]);
		stp[u][i+1] = stp[stp[u][i]][i];
	}

	int m1 = inf, m2 = inf, m3 = inf;
	for (auto [i, id2] : nei[u]){
		if (Edg[id2] < m1)
			m3 = m2, m2 = m1, m1 = Edg[id2];
		else if (Edg[id2] < m2)
			m3 = m2, m2 = Edg[id2];
		else
			m3 = min(m3, Edg[id2]);

		if (id == id2)
			continue;
		if (seen[i] == 1 and hei[i] < hei[u]){
			int d = hei[u] - hei[i], vr = u, wei = Edg[id2];
			for (int i=0;i<17;i++){
				if ((1<<i) & d)
					wei = max(wei, Mx[vr][i]), vr = stp[vr][i];
			}
			MinTrg[i] = min(MinTrg[i], wei);
		}
		if (!seen[i])
			dfs(i, u, id2);
	}

	MinTrg[u] = min(MinTrg[u], m3);
}

void dfs1(int u){
	for (auto [i, w] : nei2[u]){
		dfs1(i);
		MinTrg[u] = min(MinTrg[u], max(MinTrg[i], w));
	}
}

void dfs2(int u, int p = 0){
	hei[u] = hei[p] + 1;
	for (auto [i, w] : nei2[u]){
		MinTrg[i] = min(MinTrg[i], max(MinTrg[u], w));
		dfs2(i, u);
	}
}

int root(int v){
	while (Par[v])
		v = Par[v];
	return v;
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
	for (int i=1;i<=n;i++)
		Sz[i] = 1;
	for (int i=0;i<m;i++){
		u[i]++, v[i]++;
		Edg[i] = w[i];
		nei[u[i]].push_back({v[i], i});
		nei[v[i]].push_back({u[i], i});
		Ed.push_back({w[i], i});
	}

	dfs(1, 0, N-1);

	sort(begin(Ed), end(Ed));

	for (auto [c, i] : Ed){
		int A = root(u[i]), B = root(v[i]);
		if (A == B)
			continue;

		if (Sz[A] < Sz[B])
			swap(A, B);

		Par[B] = A, Sz[A] += Sz[B], Edge[B] = c;
		nei2[A].push_back({B, c});
	}
	dfs1(root(1));
	dfs2(root(1));
}

int getMinimumFuelCapacity(int u, int v){
	u++, v++;
	int ans = min(MinTrg[u], MinTrg[v]);

	if (hei[u] > hei[v])
		swap(u, v);

	while (hei[v] > hei[u])
		ans = max(ans, Edge[v]), v = Par[v];

	while (u != v)
		ans = max(ans, max(Edge[u], Edge[v])), v = Par[v], u = Par[u];

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

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