Submission #1191689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191689		lovrot	Swapping Cities (APIO20_swap)	C++20	6 / 100	94 ms	15652 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] ++;
	mxd[u_] = max(mxd[u_], deg[u]);
	mxd[v_] = max(mxd[v_], deg[v]);

	int t = ++newn;

	weg[t] = w;
	mxd[t] = max(mxd[u_], mxd[v_]);
	cyc[t] = cyc[u_] | cyc[v_] | (u_ == v_);	

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

vector<pair<int, pii>> swe;

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);
	}

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

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

//		printf("%d %d %d\n", i, par[i], weg[i]);

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

		l[i] = N;
		r[i] = -1;
	}

	for(int i = 0; i < newn; ++i) { 
		if(i < n) { 
			l[i] = r[i] = i;
		}
		l[par[i]] = min(l[par[i]], l[i]);
		r[par[i]] = max(r[par[i]], r[i]);
	}
}

bool ok(int u, int v) { 
	return (cyc[u] || mxd[u] >= 3) && (l[u] <= v && 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: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27