Submission #975220

#	Time	Username	Problem	Language	Result	Execution time	Memory
975220		XXBabaProBerkay	Swapping Cities (APIO20_swap)	C++17	0 / 100	2071 ms	524288 KiB

swap

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

#define F first
#define S second

using ll = long long;

const int INF = 1e9 + 7;

vector<int> dpth;
vector<vector<pair<int, int>>> adj;
vector<array<int, 20>> up, ans, res;

void DFS(int k, int p, int x);

bool comp(pair<int, int> a, pair<int, int> b)
{
	return a.S < b.S;
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
	adj.resize(N);
	dpth.resize(N);
	up = ans = res = vector<array<int, 20>>(N);
	for (int i = 0; i < M; i++)
	{
		adj[U[i]].emplace_back(V[i], W[i]);
		adj[V[i]].emplace_back(U[i], W[i]);
	}

	for (int i = 0; i < N; i++)
		sort(adj[i].begin(), adj[i].end(), comp);

	res[0][0] = INF;
	DFS(0, 0, INF);
}

void DFS(int k, int p, int x)
{
	dpth[k] = dpth[p] + 1;
	up[k][0] = p;
	ans[k][0] = x;
	for (int i = 1; i < 20; i++)
	{
		up[k][i] = up[up[k][i - 1]][i - 1];
		ans[k][i] = min(ans[k][i - 1], ans[up[k][i - 1]][i - 1]);
		res[k][i] = max(res[k][i - 1], res[up[k][i - 1]][i - 1]);
	}

	int mn = INF, mn2 = INF;
	for (pair<int, int> i : adj[k])
		if (i.F == p)
			continue;
		else if (i.S < mn)
		{
			mn2 = mn;
			mn = i.S;
		}
		else if (i.S < mn2)
			mn2 = i.S;

	for (pair<int, int> i : adj[k])
	{
		if (i.F == p)
			continue;

		res[i.F][0] = i.S;

		if (i.S == mn)
			DFS(i.F, k, mn2);
		else
			DFS(i.F, k, mn);
	}
}

array<int, 3> kth_ancestor(int a, int x)
{
	int as = INF, rs = -INF;
	for (int i = 0; i < 20; i++)
	{
		if (x & (1 << i))
		{
			as = min(as, ans[a][i]);
			rs = max(rs, res[a][i]);
			a = up[a][i];
		}
	}

	return {a, as, rs};
}

int getMinimumFuelCapacity(int X, int Y)
{
	if (dpth[X] < dpth[Y])
		swap(X, Y);

	int X0 = X, Y0 = Y;
	array<int, 3> ret = kth_ancestor(X, dpth[X] - dpth[Y]);

	if (ret[0] == Y)
	{
		ret = kth_ancestor(X, dpth[X] - dpth[Y] - 1);
		return (ret[1] == INF ? -1 : max(ret[1], ret[2]));
	}

	X = ret[0];

	for (int i = 19; i >= 0; i--)
		if (up[X][i] != up[Y][i])
			X = up[X][i], Y = up[Y][i];

	array<int, 3> rs1 = kth_ancestor(X0, dpth[X0] - dpth[X]);
	array<int, 3> rs2 = kth_ancestor(Y0, dpth[Y0] - dpth[Y]);

	int mn = INF, x = -INF, y = -INF;
	for (pair<int, int> i : adj[up[X][0]])
	{
		if (i.F == X || i.F == Y)
			continue;

		mn = min(mn, i.S);
		break;
	}

	rs1[1] = min(rs1[1], mn);
	rs1[2] = max(rs1[2], res[X][0]);
	rs2[2] = max(rs2[2], res[Y][0]);
	return (rs1[1] != INF || rs2[1] != INF ? max(max(rs1[2], rs2[2]), min(rs1[1], rs2[1])) : -1);
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:118:16: warning: unused variable 'x' [-Wunused-variable]
  118 |  int mn = INF, x = -INF, y = -INF;
      |                ^
swap.cpp:118:26: warning: unused variable 'y' [-Wunused-variable]
  118 |  int mn = INF, x = -INF, y = -INF;
      |                          ^

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