Submission #292355

#	Time	Username	Problem	Language	Result	Execution time	Memory
292355		luciocf	Swapping Cities (APIO20_swap)	C++14	100 / 100	314 ms	22264 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

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

int n;
int mn3[maxn];

int ans[maxn];

int D[maxn], par[maxn];
bool mark[maxn];

vector<pii> grafo[maxn];

struct Edge
{
	int u, v, w;
} edge[maxn];

struct DSU
{
	int pai[maxn], peso[maxn], nivel[maxn], val[maxn], tt[maxn];
 
	void init(int n)
	{
		for (int i = 1; i <= n; i++)
		{
			pai[i] = i, peso[i] = 1, nivel[i] = 0;

			if (grafo[i].size() >= 3) val[i] = mn3[i];
			else val[i] = inf;
		}
	}
 
	int Find(int x)
	{
		if (pai[x] == x) return x;
		return Find(pai[x]);
	}
 
	void Join(int x, int y, int t)
	{
		x = Find(x), y = Find(y);
		if (x == y) return;
 
		if (peso[x] < peso[y]) swap(x, y);
 
		pai[y] = x, peso[x] += peso[y], tt[y] = t;
	}

	void dfs(int u)
	{
		if (u == Find(u))
		{
			nivel[u] = 1;
			return;
		}
 
		if (!nivel[pai[u]]) dfs(pai[u]);
		nivel[u] = nivel[pai[u]]+1;
	}

	void upd(int u)
	{
		int v = u;
		int mx = 0;

		while (true)
		{
			val[v] = min(val[v], max(mn3[u], mx));

			if (pai[v] == v) return;

			mx = max(mx, tt[v]);
			v = pai[v];
		}
	}

	int get(int u)
	{
		int v = u, ans = inf, mx = 0;

		while (true)
		{
			ans = min(ans, max(mx, val[v]));

			if (v == pai[v]) return ans;

			mx = max(mx, tt[v]);
			v = pai[v];
		}
	}

	int get_mx(int u, int v)
	{
		int ans = 0;
 
		while (u != v)
		{
			if (nivel[u] > nivel[v])
			{
				ans = max(ans, tt[u]);
				u = pai[u];
			}
			else
			{
				ans = max(ans, tt[v]);
				v = pai[v];
			}
		}
 
		return ans;
	}

} dsu;

void init(int N, int m, vector<int> U, vector<int> V, vector<int> W)
{
	n = N;

	for (int i = 0; i < m; i++)
	{
		grafo[U[i]+1].push_back({V[i]+1, W[i]});
		grafo[V[i]+1].push_back({U[i]+1, W[i]});

		edge[i+1] = {U[i]+1, V[i]+1, W[i]};
	}

	sort(edge+1, edge+m+1, [&] (Edge a, Edge b) {return a.w < b.w;});

	for (int i = 1; i <= n; i++)
	{
		sort(grafo[i].begin(), grafo[i].end(), [&] (pii a, pii b) {return a.ss < b.ss;});

		if (grafo[i].size() <= 2) mn3[i] = inf;
		else mn3[i] = grafo[i][2].ss;
	}

	dsu.init(n);

	for (int i = 1; i <= m; i++)
	{
		if (dsu.Find(edge[i].u) == dsu.Find(edge[i].v))
		{
			mn3[edge[i].u] = min(mn3[edge[i].u], edge[i].w);
			mn3[edge[i].v] = min(mn3[edge[i].v], edge[i].w);
		}
		
		dsu.Join(edge[i].u, edge[i].v, edge[i].w);
	}

	for (int i = 1; i <= n; i++)
	{
		if (mn3[i] != inf)
			dsu.upd(i);

		if (!dsu.nivel[i])
			dsu.dfs(i);
	}
}

int getMinimumFuelCapacity(int u, int v)
{
	u++, v++;
	if (u == v) return -1;

	if (min(dsu.get(u), dsu.get(v)) == inf) return -1;

	return max(min(dsu.get(u), dsu.get(v)), dsu.get_mx(u, v));
}

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