Submission #576459

#	Time	Username	Problem	Language	Result	Execution time	Memory
576459		pnm1384	Swapping Cities (APIO20_swap)	C++14	0 / 100	236 ms	50268 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second

const int N = 1e5 + 20, M = 2e5 + 20, LG = 20;
vector<pair<int, int>> adj[N], vt[N];
int par2[N], sz[N], bala[LG][N], mn_cross[LG][N], ch[N], h[N], par[LG][N], bad[LG][N], cost_mn_pair[N];
pair<int, pair<int, int>> edg[M];
pair<int, int> mn_pair[N];
int n, m;

int Find(int u)
{
	if (u == par2[u]) return u;
	return par2[u] = Find(par2[u]);
}

inline void mer(int u, int v)
{
	u = Find(u); v = Find(v);
	if (u == v) return;
	if (sz[v] > sz[u]) swap(u, v);
	sz[u] += sz[v];
	par2[v] = u;
	return;
}

void dfs(int u, int pp = -1)
{
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F, w = ppp.S;
		if (v == pp) continue;
		bala[0][v] = w;
		ch[u] = min(ch[u], w);
		par[0][v] = u;
		h[v] = h[u] + 1;
		dfs(v, u);
	}
	int mx = 1e9 + 10;
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F, w = ppp.S;
		if (v == pp) continue;
		bad[0][v] = min(bad[0][v], mx);
		mx = min(mx, w);
	}
	mx = 1e9 + 10;
	for (int i = (int)adj[u].size() - 1; i > -1; i--)
	{
		int v = adj[u][i].F, w = adj[u][i].S;
		if (v == pp) continue;
		bad[0][v] = min(bad[0][v], mx);
		mx = min(mx, w);
	}
	return;
}

inline int get_bala(int u, int k)
{
	int ans = 0;
	for (int i = 0; i < LG; i++)
	{
		if ((k >> i) & 1)
		{
			ans = max(ans, bala[i][u]);
			u = par[i][u];
		}
	}
	return ans;
}

inline int get_par(int u, int k)
{
	for (int i = 0; i < LG; i++)
	{
		if ((k >> i) & 1) u = par[i][u];
	}
	return u;
}

inline int lca(int u, int v)
{
	if (h[u] > h[v]) swap(u, v);
	v = get_par(v, h[v] - h[u]);
	if (u == v) return u;
	for (int i = LG - 1; i > -1; i--)
	{
		if (par[i][u] != par[i][v])
		{
			u = par[i][u];
			v = par[i][v];
		}
	}
	return par[0][u];
}

inline int get_bad(int u, int k)
{
	int ans = 1e9 + 10;
	for (int i = 0; i < LG; i++)
	{
		if ((k >> i) & 1)
		{
			ans = min(ans, bad[i][u]);
			u = par[i][u];
		}
	}
	return ans;
}

inline int get_cross(int u, int k)
{
	int ans = 1e9 + 10;
	for (int i = 0; i < LG; i++)
	{
		if ((k >> i) & 1)
		{
			ans = min(ans, mn_cross[i][u]);
			u = par[i][u];
		}
	}
	return ans;
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
	memset(cost_mn_pair, 63, sizeof cost_mn_pair);
	memset(bad, 63, sizeof bad);
	memset(ch, 63, sizeof ch);
	memset(mn_cross, 63, sizeof mn_cross);
	memset(bala, 63, sizeof bala);
	n = N; m = M;
	for (int i = 0; i < n; i++)
	{
		par2[i] = i; sz[i] = 1;
	}
	for (int i = 0; i < m; i++)
	{
		edg[i] = {W[i], {U[i], V[i]}};
	}
	sort(edg, edg + M);
	for (int i = 0; i < m; i++)
	{
		int w = edg[i].F, u = edg[i].S.F, v = edg[i].S.S;
		if (Find(u) != Find(v))
		{
			mer(u, v);
			adj[u].push_back({v, w});
			adj[v].push_back({u, w});
			vt[u].push_back({w, v});
			vt[v].push_back({w, u});
		}
		else
		{
			mn_cross[0][u] = min(mn_cross[0][u], w);
			mn_cross[0][v] = min(mn_cross[0][v], w);
		}
	}
	for (int u = 0; u < n; u++)
	{
		sort(vt[u].begin(), vt[u].end());
		if ((int)adj[u].size() <= 2) continue;
		int x = vt[u][0].S, y = vt[u][1].S;
		if (x > y) swap(x, y);
		mn_pair[u] = {x, y};
		cost_mn_pair[u] = vt[u][2].F;
	}
	dfs(0);
	for (int k = 1; k < LG; k++)
	{
		for (int u = 0; u < n; u++)
		{
			par[k][u] = par[k - 1][par[k - 1][u]];
			bad[k][u] = min(bad[k - 1][u], bad[k - 1][par[k - 1][u]]);
			mn_cross[k][u] = min(mn_cross[k - 1][u], mn_cross[k - 1][par[k - 1][u]]);
			bala[k][u] = max(bala[k - 1][u], bala[k - 1][par[k - 1][u]]);
		}
	}
}

int getMinimumFuelCapacity(int X, int Y) 
{
	int u = X, v = Y;
	int w = lca(u, v);
	int masir = max(get_bala(u, h[u] - h[w]), get_bala(v, h[v] - h[w]));
	int ans = 1e9 + 10;
	if (h[u] >= h[w] + 2) ans = min(ans, get_bad(u, h[u] - h[w] - 1));
	if (h[v] >= h[w] + 2) ans = min(ans, get_bad(v, h[v] - h[w] - 1));
	ans = min(ans, get_cross(u, h[u] - h[w] + 1));
	ans = min(ans, get_cross(v, h[v] - h[w] + 1));
	if (u != w) ans = min(ans, ch[u]);
	if (v != w) ans = min(ans, ch[v]);
	if (w != 0) ans = min(ans, bala[0][w]);
	if (u == w || v == w)
	{
		int vert = u;
		if (u == w) vert = v;
		vert = get_par(vert, h[vert] - h[w] - 1);
		ans = min(ans, bad[0][vert]);
	}
	else
	{
		u = get_par(u, h[u] - h[w] - 1);
		v = get_par(v, h[v] - h[w] - 1);
		if (u > v) swap(u, v);
		pair<int, int> pp = {u, v};
		if (pp == mn_pair[w]) ans = min(ans, cost_mn_pair[w]);
		else ans = -1;
	}
	if (ans > 1e9) return -1;
	return min(ans, masir);
}

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