Submission #347075

#	Time	Username	Problem	Language	Result	Execution time	Memory
347075		patrikpavic2	Swapping Cities (APIO20_swap)	C++17	100 / 100	374 ms	17244 KiB

swap

#include "swap.h"

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef vector < int > vi;
typedef pair < int, int > pii;

const int N = 2e5 + 500;
const int INF = 0x3f3f3f3f;
const int LOG = 18;

int par[N], kad[N], postao[N], siz[N], deg[N];
vector < pair < int, pii > > edg;

int pr(int x, int tren){
	if(par[x] == x || kad[x] > tren) 
		return x;
	return pr(par[x], tren);
}

void mrg(int x, int y, int z){
	if(pr(x, z) == pr(y, z)){
		x = pr(x, z);
		postao[x] = min(postao[x], z);
		return;
	}
	deg[x]++; deg[y]++;
	bool dobar = (deg[x] >= 3 || deg[y] >= 3);
	x = pr(x, z), y = pr(y, z);
	if(siz[x] < siz[y])
		{x ^= y, y ^= x, x ^= y;}
	par[y] = x; kad[y] = z;
	siz[x] += siz[y];
	postao[x] = min(postao[x], max(postao[y], z));
	if(dobar)
		postao[x] = min(postao[x], z);
}


void init(int n, int m, vi U, vi V, vi W) {
	for(int i = 0;i < m;i++)
		edg.PB({W[i], {U[i], V[i]}});
	for(int i = 0;i < n;i++)
		par[i] = i, siz[i] = 1, postao[i] = INF;
	sort(edg.begin(), edg.end());
	for(pair < int, pii > cur : edg){
		mrg(cur.Y.X, cur.Y.Y, cur.X);
	}
}

bool probaj(int x, int y, int z){
	x = pr(x, z); y = pr(y, z);
	if(x != y)
		return 0;
	return (z >= postao[x]);
}


int getMinimumFuelCapacity(int x, int y){
	int ret = -1;
	for(int i = 30;i >= 0;i--)
		if(!probaj(x, y, ret + (1 << i)))
			ret += (1 << i);
	if(ret + 1 == INF)
		return -1;
	return ret + 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