Submission #1288612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288612		Jawad_Akbar_JJ	Swapping Cities (APIO20_swap)	C++20	100 / 100	138 ms	22292 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], Par[N],hei[N], MinTrg[N], seen[N], Sz[N], inf = 1e9 + 7;

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=0;i<m;i++){
		u[i]++, v[i]++;
		nei[u[i]].push_back({v[i], w[i]});
		nei[v[i]].push_back({u[i], w[i]});
		Ed.push_back({w[i], i});
	}

	for (int u=1;u<=n;u++){
		int m1 = inf, m2 = inf, m3 = inf;

		for (auto [i, w] : nei[u]){
			if (w < m1)
				m3 = m2, m2 = m1, m1 = w;
			else if (w < m2)
				m3 = m2, m2 = w;
			else
				m3 = min(m3, w);
		}

		MinTrg[u] = m3, Sz[u] = 1;
	}

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

	for (auto [c, i] : Ed){
		int A = root(u[i]), B = root(v[i]);
		if (A == B){
			MinTrg[A] = min(MinTrg[A], c);
			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: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27