Submission #51894

#	Time	Username	Problem	Language	Result	Execution time	Memory
51894		faremy	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1126 ms	52268 KiB

plan

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>

#define setbits(x) __builtin_popcount(x)
#define all(a) std::begin(a), std::end(a)
#define all_r(a, n) std::begin(a), std::begin(a) + n


struct Edge
{
	Edge(int d, int w) : destination(d), weight(w) {}
	int destination, weight;

	bool operator <(const Edge &other) const
	{
		return (other.weight < weight);
	}
};


const int MAXN = 1e5, MAXM = 5e5;
const int INFTY = 1e9;

int start[MAXM], end[MAXM];
int weight[MAXM];
std::vector<Edge> graph[MAXN];

std::priority_queue<Edge> next;
int safety[MAXN];

int kruskal[MAXM];
int unionFind[MAXN];
std::vector<Edge> mst[MAXN];

int depth[MAXN], lgDepth[MAXN];
int parent[MAXN], pWeight[MAXN];
int ancester[MAXN][17], aWeight[MAXN][17];


void dijkstra()
{
	while (!next.empty())
	{
		int node = next.top().destination;
		int distance = next.top().weight;
		next.pop();

		if (safety[node] != -1)
			continue;
		safety[node] = distance;

		for (const Edge &edge : graph[node])
			next.emplace(edge.destination, distance + edge.weight);
	}
}

int find(int node)
{
	if (node == unionFind[node])
		return node;
	unionFind[node] = find(unionFind[node]);
	return unionFind[node];
}

void add(int edge)
{
	if (find(start[edge]) != find(end[edge]))
	{
		unionFind[find(end[edge])] = find(start[edge]);
		mst[start[edge]].emplace_back(end[edge], weight[edge]);
		mst[end[edge]].emplace_back(start[edge], weight[edge]);
	}
}

void setdepth(int node, int cDepth)
{
	for (const Edge &edge : mst[node])
		if (edge.destination != parent[node])
		{
			parent[edge.destination] = node;
			pWeight[edge.destination] = edge.weight;

			depth[edge.destination] = cDepth;
			lgDepth[edge.destination] = log2(cDepth);
			setdepth(edge.destination, cDepth + 1);
		}
}

int getancester(int node, int power)
{
	if (ancester[node][power] == -1)
	{
		if (power == 0)
		{
			ancester[node][power] = parent[node];
			aWeight[node][power] = pWeight[node];
		}
		else
		{
			ancester[node][power] = getancester(getancester(node, power - 1), power - 1);
			aWeight[node][power] = std::min(aWeight[node][power - 1], aWeight[ancester[node][power - 1]][power - 1]);
		}
	}

	return ancester[node][power];
}

int lift(int node, int generation)
{
	if (generation == 0)
		return node;
	int power = log2(generation);
	return lift(getancester(node, power), generation - (1 << power));
}

int liftWeight(int node, int generation)
{
	if (generation == 0)
		return INFTY;
	int power = log2(generation);
	return std::min(liftWeight(getancester(node, power), generation - (1 << power)), aWeight[node][power]);
}

int lca(int u, int v)
{
	if (depth[u] < depth[v])
		std::swap(u, v);
	u = lift(u, depth[u] - depth[v]);

	if (u == v)
		return u;
	for (int power = lgDepth[u]; power > -1; power = std::min(power - 1, lgDepth[u]))
		if (getancester(u, power) != getancester(v, power))
		{
			u = ancester[u][power];
			v = ancester[v][power];
		}

	return parent[u];
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(nullptr);
	std::cin.tie(nullptr);

	int nodes, edges;
	std::cin >> nodes >> edges;

	for (int iEdge = 0; iEdge < edges; iEdge++)
	{
		std::cin >> start[iEdge] >> end[iEdge] >> weight[iEdge];
		start[iEdge]--; end[iEdge]--;
		graph[start[iEdge]].emplace_back(end[iEdge], weight[iEdge]);
		graph[end[iEdge]].emplace_back(start[iEdge], weight[iEdge]);
	}

	int danger; std::cin >> danger;
	for (int iNpp = 0; iNpp < danger; iNpp++)
	{
		int npp; std::cin >> npp;
		next.emplace(npp - 1, 0);
	}

	std::fill_n(safety, nodes, -1);
	dijkstra();

	for (int iEdge = 0; iEdge < edges; iEdge++)
	{
		weight[iEdge] = std::min(safety[start[iEdge]], safety[end[iEdge]]);
		kruskal[iEdge] = iEdge;
	}

	std::sort(all_r(kruskal, edges), [](const int &a, const int &b) { return (weight[a] > weight[b]); });
	for (int iNode = 1; iNode < nodes; iNode++)
		unionFind[iNode] = iNode;

	for (int iEdge = 0; iEdge < edges; iEdge++)
		add(kruskal[iEdge]);
	setdepth(0, 1);
	std::fill_n((int *)ancester, nodes * 17, -1);

	int queries ; std::cin >> queries;
	for (int iQuery = 0; iQuery < queries; iQuery++)
	{
		int from, to;
		std::cin >> from >> to;
		from--; to--;

		int intermediary = lca(from, to);
		int firstHalf = liftWeight(from, depth[from] - depth[intermediary]);
		int secondHalf = liftWeight(to, depth[to] - depth[intermediary]);
		std::cout << std::min(firstHalf, secondHalf) << '\n';
	}

	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46