Submission #1191732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191732		lovrot	Swapping Cities (APIO20_swap)	C++20	100 / 100	155 ms	40808 KiB

swap

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include "swap.h"

#define X first
#define Y second
#define PB push_back
#define deb(...) //fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int LOG = 19;
const int N = 1 << LOG;

int un[N], jmp[N], par[N], dep[N];
int mxd[N], cyc[N], deg[N], weg[N], newn;
int l[N], r[N];

int trazi(int u) { return un[u] == -1 ? u : un[u] = trazi(un[u]); }

void unija(int u, int v, int w) { 
	int u_ = trazi(u);
	int v_ = trazi(v);

	deg[u] ++;
	deg[v] ++;

	int t = ++newn;

	weg[t] = w;
	mxd[t] = max({mxd[u_], mxd[v_], deg[u], deg[v]});
	cyc[t] = cyc[u_] | cyc[v_] | (u_ == v_);	

	par[u_] = par[v_] = t;
	un[u_] = un[v_] = t;
}

vector<pair<int, pii>> swe;
vector<int> g[N];

void dfs(int u, int &k) { 
	l[u] = k;
	k += g[u].empty();
	for(int v : g[u]) { dfs(v, k); }
	r[u] = k;
}

void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
	newn = n - 1;
	memset(un, -1, sizeof(un));
	
	for(int i = 0; i < m; ++i) { swe.PB({W[i], {U[i], V[i]}}); }

	sort(swe.begin(), swe.end());

	for(pair<int, pii> &i : swe) { 
		unija(i.Y.X, i.Y.Y, i.X);
		deb("%d %d %d\n", i.Y.X, i.Y.Y, i.X);
	}

	deb("\n");

	jmp[newn] = newn;
	dep[newn] = 0;
	par[newn] = -1;

	for(int i = newn - 1; i >= 0; --i) { 
		int p = par[i];
		g[p].PB(i);
		dep[i] = dep[p] + 1;

		deb("%d %d %d, %d %d\n", i, par[i], weg[i], cyc[i], mxd[i]);

		if(dep[p] - dep[jmp[p]] == dep[jmp[p]] - dep[jmp[jmp[p]]]) { 
			jmp[i] = jmp[jmp[p]];
		} else {
			jmp[i] = p;
		}
	}

	int k = 0;
	dfs(newn, k);
}

bool ok(int u, int v) { 
	return (cyc[u] || mxd[u] >= 3) && (l[u] <= l[v] && r[v] <= r[u]);
}

int getMinimumFuelCapacity(int x, int y) { 
	if(x == y) { return 0; }

	for(; !ok(x, y); ) { 
		if(ok(jmp[x], y)) { x = par[x]; }
		else {
			if(jmp[x] == x) { return -1; }
			x = jmp[x];
		}
	}

	return weg[x];
}

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