Submission #294917

#	Time	Username	Problem	Language	Result	Execution time	Memory
294917		Berted	Swapping Cities (APIO20_swap)	C++14	100 / 100	512 ms	45804 KiB

swap

#include "swap.h"

#include <vector>
#include <iostream>
#include <algorithm>
#include <assert.h>
#define pii pair<int, int>
#define fst first
#define snd second
#define ppi pair<pii, int>
#define vi vector<int>
using namespace std;

const int INF = 1e9, LG = 19;

ppi edge[200001];
int par[100001], cur[100001], idx, deg[100001];

vi tree[300001];
int sps[300001][LG], val[300001], h[300001];
bool st[300001];

inline bool comp(const ppi &l, const ppi &r)
{
	return make_pair(l.snd, l.fst) < make_pair(r.snd, r.fst);
}

int fn(int x) {return par[x] = (par[x] == x) ? x : fn(par[x]);}
void jn(int a, int b, int v)
{	
	deg[a]++; deg[b]++;
	bool ck = (deg[a] > 2) || (deg[b] > 2);
	a = fn(a), b = fn(b);
	if (a != b)
	{
		ck |= st[cur[a]] || st[cur[b]];
		par[b] = a;
		//cout << "Edge from " << idx << " -> " << cur[a] << "\n";
		//cout << "Edge from " << idx << " -> " << cur[b] << "\n";
		tree[idx].push_back(cur[a]);
		tree[idx].push_back(cur[b]);
		cur[a] = idx++;
		val[cur[a]] = v; st[cur[a]] = ck;
		//cout << "Data : " << cur[a] << " " << val[cur[a]] << " " << st[cur[a]] << "\n";
	}
	else
	{
		if (!st[cur[a]])
		{
			//cout << "Edge from " << idx << " -> " << cur[a] << "\n";
			tree[idx].push_back(cur[a]);
			cur[a] = idx++;
			val[cur[a]] = v; st[cur[a]] = 1;
			//cout << "Data : " << cur[a] << " " << val[cur[a]] << " " << st[cur[a]] << "\n";
		}
	}
}

void DFS(int u, int p)
{
	h[u] = (p == -1) ? 0 : (h[p] + 1);
	sps[u][0] = p;
	//cout << u << " " << h[u] << " " << sps[u][0] << "\n";
	for (int i = 1; i < LG; i++)
	{
		if (sps[u][i - 1] != -1) {sps[u][i] = sps[sps[u][i - 1]][i - 1];}
		else {sps[u][i] = -1;}
	}
	for (auto v : tree[u]) DFS(v, u);
}

int findLCA(int u, int v)
{
	if (h[u] > h[v]) swap(u, v);
	for (int i = 0; h[v] - h[u]; i++) 
	{
		assert(i < LG);
		if ((h[v] - h[u]) & (1 << i)) v = sps[v][i];
	}
	if (u == v) return u;
	for (int i = LG - 1; i >= 0; i--)
	{
		if (sps[u][i] != sps[v][i]) 
		{
			u = sps[u][i];
			v = sps[v][i];
		}
	}
	return sps[u][0];
}

int findValid(int x)
{
	if (st[x]) return x;
	for (int i = LG - 1; i >= 0; i--)
	{
		if (sps[x][i] != -1 && !st[sps[x][i]]) {x = sps[x][i];}
	}
	return sps[x][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) 
{
	for (int i = 0; i < N; i++)
	{
		cur[i] = i; deg[i] = 0; par[i] = i;
	}
	idx = N;
	for (int i = 0; i < M; i++)
	{
		edge[i] = {{U[i], V[i]}, W[i]};
	}
	sort(edge, edge + M, comp);
	for (int i = 0; i < M; i++)
	{
		jn(edge[i].fst.fst, edge[i].fst.snd, edge[i].snd);
	}
	DFS(idx - 1, -1);
}

int getMinimumFuelCapacity(int X, int Y) 
{
	if (!st[idx - 1]) return -1;
	else
	{
		int L = findLCA(X, Y);
		return val[findValid(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