Submission #576604

#	Time	Username	Problem	Language	Result	Execution time	Memory
576604		pooyashams	Swapping Cities (APIO20_swap)	C++14	100 / 100	217 ms	28712 KiB

swap

#include "swap.h"
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 2e5+10;
const int lgmx = 18;
const int inf = 1e9+69;

struct edge
{
	int x, y, z;
	inline bool operator<(const edge& o) const
	{
		return z < o.z;
	}
} edgs[maxn];

int N, M;

vector<int> comp[maxn];
int root[maxn];
bool ispath[maxn];
int fnp[maxn];
pii sars[maxn];

int epar[maxn];
int dpar[maxn];
vector<int> kids[maxn];

inline void invldp(int r, int z)
{
	if(!ispath[r]) return;
	for(int u: comp[r])
	{
		//if(!ispath[u])
		//	cerr << "fuck" << endl;
		ispath[u] = false;
		fnp[u] = z;
	}
}

inline bool isin(int x, pii p)
{
	return x == p.first or x == p.second;
}

inline void mrg(int x, int y, int z)
{
	if(comp[root[x]].size() < comp[root[y]].size())
		swap(x, y);
	int rx = root[x];
	int ry = root[y];
	if(rx == ry)
	{
		invldp(rx, z);
	}
	else
	{
		if( ispath[rx] and ispath[ry] and isin(x, sars[rx]) and isin(y, sars[ry]) )
		{
			int a = sars[rx].first^sars[rx].second ^ x;
			int b = sars[ry].first^sars[ry].second ^ y;
			sars[rx] = pii(a, b);
		}
		else
		{
			invldp(rx, z);
			invldp(ry, z);
		}
		epar[ry] = z;
		dpar[ry] = rx;
		for(int u: comp[ry])
		{
			root[u] = rx;
			comp[rx].push_back(u);
		}
		comp[ry].clear();
	}
}

int tin[maxn];
int tout[maxn];
int timer = 0;

void dfs(int v)
{
	tin[v] = timer++;
	for(int u: kids[v])
		dfs(u);
	tout[v] = timer;
}

inline bool isanc(int x, int y)
{
	return (tin[x] <= tin[y] and tout[y] <= tout[x]);
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
	::N = N;
	::M = M;
	for(int i = 0; i < N; i++)
	{
		root[i] = i;
		comp[i].push_back(i);
		ispath[i] = true;
		fnp[i] = inf;
		sars[i] = pii(i, i);
		dpar[i] = i;
	}
	for(int i = 0; i < M; i++)
		edgs[i] = {V[i], U[i], W[i]};
	sort(edgs, edgs+M);
	for(int i = 0; i < M; i++)
	{
		int x = edgs[i].x;
		int y = edgs[i].y;
		int z = edgs[i].z;
		mrg(x, y, z);
	}
	int r = 0;
	for(int i = 0; i < N; i++)
	{
		if(dpar[i] != i)
			kids[dpar[i]].push_back(i);
		else
			r = i;
	}
	//cerr << r << endl;
	dfs(r);
}

int getMinimumFuelCapacity(int x, int y)
{
	int ans = max(fnp[x], fnp[y]);
	int v = x;
	int t = 0;
	while(!isanc(v, y))
	{
		ans = max(ans, epar[v]);
		v = dpar[v];
		t++;
	}
	assert(t <= lgmx);
	t = 0;
	v = y;
	while(!isanc(v, x))
	{
		ans = max(ans, epar[v]);
		v = dpar[v];
		t++;
	}
	//cerr << t << endl;
	assert(t <= lgmx);
	if(ans == inf)
		return -1;
	return ans;
}

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