Submission #1176490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176490		tkm_algorithms	Swapping Cities (APIO20_swap)	C++20	100 / 100	251 ms	70980 KiB

swap

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
//#define int ll
const char nl = '\n';
const int N = 3e5+10;
const int inf = 1e9;

int p[N+1], sw[N+1], deg[N+1], we[N+1], dep[N+1];
int par[N+1][30];
vector<int> taze[N+1];
vector<pair<int, pair<int, int>>> g;

int get(int u) {
	if (p[u] != u)return p[u] = get(p[u]);
	return u;
}

void build(int u, int pr) {
	par[u][0] = pr;
	//if (u == 4)cout << pr << nl;
	for (int i = 1; i < 30; ++i) {
		if ((1 << i) > dep[u])break;
		par[u][i] = par[par[u][i-1]][i-1];
	}
	
	for (auto i: taze[u]) {
		if (i == pr)continue;
		dep[i] = dep[u] + 1;
		build(i, u);
	}
}

int lca(int u, int v) {
	if (dep[u] < dep[v])swap(u, v);
	
	for (int i = 29; i >= 0; --i) {
		if (par[u][i] == -1)continue;
		if (dep[par[u][i]] >= dep[v])u = par[u][i]; 
	}
	
	//cout << u << " " << v << nl;
	
	if (u == v)return u;
	
	for (int i = 29; i >= 0; --i)
		if (par[u][i] != par[v][i]) {
			u = par[u][i], v = par[v][i];
		}
	
	return par[u][0];
}

void init(int n, int m, vector<int> ue, vector<int> ve, vector<int> wee) {
	memset(par, -1, sizeof par);
	for (int i = 0; i < m; ++i) {
		g.push_back({wee[i], {ue[i], ve[i]}});
	}
	
	for (int i = 0; i <= N; ++i)
		p[i] = i, sw[i] = 0, deg[i] = 0;
		
	int add = n;
	sort(all(g));
	for (auto i: g) {
		int w, u, v;
		w = i.first, u = i.second.first, v = i.second.second;
		
		int gt1 = get(u), gt2 = get(v);
		p[gt1] = p[gt2] = add;
		add += 1;
		
		//cout << w << nl;
		
		if (gt1 == gt2) {// cycle
			sw[add-1] = 1, we[add-1] = w;
			taze[add-1].push_back(gt1);
		} else {
			
			taze[add-1].push_back(gt1);
			taze[add-1].push_back(gt2);
			deg[u] += 1, deg[v] += 1;
			if (max(deg[u], deg[v]) >= 3 || max(sw[gt1], sw[gt2]) == 1)sw[add-1] = 1;
			we[add-1] = w; 
			
		}
	}
	
	build(add-1, 0);
}

int getMinimumFuelCapacity(int u, int v) {
	int l = lca(u, v);
	if (sw[l] == 1)return we[l];
	for (int i = 29; i >= 0; --i) {
		if (par[l][i] == -1)continue;
		if (sw[par[l][i]] != 1)l = par[l][i];
	}
	
	l = par[l][0];
	if (l == -1 || sw[l] == 0)return -1;
	return we[l];
}

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