Submission #292514

#	Time	Username	Problem	Language	Result	Execution time	Memory
292514		amoo_safar	Swapping Cities (APIO20_swap)	C++17	100 / 100	425 ms	38376 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;

const int N = 3e5 + 10;
const int Log = 20;


vector<pair<int, pii>> E;

int sp[Log][N], dep[N], wp[N];
int par[N], gd[N], la;
int deg[N], n, m;

int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}
void Unite(int u, int v, int w){
	u = Find(u);
	v = Find(v);
	if(u == v){
		la ++;
		gd[la] = 1;
		par[u] = la;
		wp[u] = w;
		sp[0][u] = la;
		return ;
	}

	la ++;
	par[u] = la;
	par[v] = la;

	wp[u] = w;
	wp[v] = w;
	
	sp[0][u] = la;
	sp[0][v] = la;


	gd[la] = gd[v] | gd[u];
}

void init(int n2, int m2, vector<int> U, vector<int> V, vector<int> W) {
	n = n2;
	m = m2;
	for(int i = 0; i < m; i++)
		E.pb({W[i], {U[i], V[i]}});
	
	la = n - 1;
	sort(all(E));

	memset(gd, 0, sizeof gd);
	memset(deg, 0, sizeof deg);
	iota(par, par + N, 0);
	memset(sp, 0, sizeof sp);
	memset(wp, 0, sizeof wp);
	memset(dep, 0, sizeof dep);

	int u, v, w;
	for(auto ob : E){
		u = ob.S.F;
		v = ob.S.S;
		w = ob.F;
		Unite(u, v, w);
		deg[u] ++;
		deg[v] ++;
		if(max(deg[u], deg[v]) >= 3){
			gd[Find(u)] = 1;
		}
	}

	sp[0][la] = la;
	for(int l = 1; l < Log; l++)
		for(int i = 0; i <= la; i++)
			sp[l][i] = sp[l - 1][sp[l - 1][i]];

	dep[la] = 0;
	for(int i = la - 1; i >= 0; i--)
		dep[i] = dep[sp[0][i]] + 1;

}

int getMinimumFuelCapacity(int X, int Y){
	if(dep[X] < dep[Y]) swap(X, Y);
	//cerr << "! " << dep[X] << ' ' << dep[Y] << '\n';
	int h = dep[X] - dep[Y];
	for(int l = 0; l < Log; l++)
		if(h >> l & 1)
			X = sp[l][X];

	for(int l = Log - 1; l >= 0; l--){
		if((sp[l][X] != sp[l][Y]) || (gd[sp[l][X]] == 0)){
			X = sp[l][X];
			Y = sp[l][Y];
		}
	}
	//cerr << "# " << X << ' ' << Y << '\n';
	int res = max(wp[X], wp[Y]);
	X = sp[0][X];
	Y = sp[0][Y];
	if((X != Y) || (gd[X] == 0))
		return -1;
	return res;
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

*/

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