oj.uz

Submission #51894

# Submission time Handle Problem Language Result Execution time Memory
51894 2018-06-22T13:02:24 Z faremy Evacuation plan (IZhO18_plan) C++14
100 / 100
 1126 ms 52268 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 7 ms 5368 KB Output is correct
4 Correct 4 ms 5112 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 7 ms 5368 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 7 ms 5340 KB Output is correct
10 Correct 7 ms 5340 KB Output is correct
11 Correct 7 ms 5368 KB Output is correct
12 Correct 7 ms 5368 KB Output is correct
13 Correct 7 ms 5368 KB Output is correct
14 Correct 7 ms 5368 KB Output is correct
15 Correct 7 ms 5368 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 7 ms 5368 KB Output is correct
4 Correct 4 ms 5112 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 7 ms 5368 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 7 ms 5340 KB Output is correct
10 Correct 7 ms 5340 KB Output is correct
11 Correct 7 ms 5368 KB Output is correct
12 Correct 7 ms 5368 KB Output is correct
13 Correct 7 ms 5368 KB Output is correct
14 Correct 7 ms 5368 KB Output is correct
15 Correct 7 ms 5368 KB Output is correct
16 Correct 236 ms 25924 KB Output is correct
17 Correct 925 ms 50312 KB Output is correct
18 Correct 60 ms 9584 KB Output is correct
19 Correct 192 ms 31372 KB Output is correct
20 Correct 934 ms 50388 KB Output is correct
21 Correct 422 ms 35372 KB Output is correct
22 Correct 171 ms 35780 KB Output is correct
23 Correct 906 ms 50440 KB Output is correct
24 Correct 914 ms 50360 KB Output is correct
25 Correct 893 ms 50388 KB Output is correct
26 Correct 185 ms 31152 KB Output is correct
27 Correct 234 ms 31248 KB Output is correct
28 Correct 196 ms 31104 KB Output is correct
29 Correct 195 ms 31276 KB Output is correct
30 Correct 192 ms 31372 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5116 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 28328 KB Output is correct
2 Correct 776 ms 43604 KB Output is correct
3 Correct 781 ms 43860 KB Output is correct
4 Correct 184 ms 32376 KB Output is correct
5 Correct 856 ms 43596 KB Output is correct
6 Correct 843 ms 43604 KB Output is correct
7 Correct 801 ms 43548 KB Output is correct
8 Correct 753 ms 43736 KB Output is correct
9 Correct 788 ms 43612 KB Output is correct
10 Correct 909 ms 43524 KB Output is correct
11 Correct 791 ms 43688 KB Output is correct
12 Correct 827 ms 43620 KB Output is correct
13 Correct 762 ms 43988 KB Output is correct
14 Correct 781 ms 43756 KB Output is correct
15 Correct 781 ms 43988 KB Output is correct
16 Correct 755 ms 43788 KB Output is correct
17 Correct 775 ms 43628 KB Output is correct
18 Correct 767 ms 43664 KB Output is correct
19 Correct 114 ms 27976 KB Output is correct
20 Correct 758 ms 43728 KB Output is correct
21 Correct 698 ms 44904 KB Output is correct
22 Correct 132 ms 24300 KB Output is correct
23 Correct 144 ms 29868 KB Output is correct
24 Correct 130 ms 24300 KB Output is correct
25 Correct 136 ms 24316 KB Output is correct
26 Correct 161 ms 30576 KB Output is correct
27 Correct 137 ms 34188 KB Output is correct
28 Correct 132 ms 24320 KB Output is correct
29 Correct 133 ms 33312 KB Output is correct
30 Correct 130 ms 24296 KB Output is correct
31 Correct 131 ms 33372 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 7 ms 5368 KB Output is correct
4 Correct 4 ms 5112 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 7 ms 5368 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 7 ms 5340 KB Output is correct
10 Correct 7 ms 5340 KB Output is correct
11 Correct 7 ms 5368 KB Output is correct
12 Correct 7 ms 5368 KB Output is correct
13 Correct 7 ms 5368 KB Output is correct
14 Correct 7 ms 5368 KB Output is correct
15 Correct 7 ms 5368 KB Output is correct
16 Correct 236 ms 25924 KB Output is correct
17 Correct 925 ms 50312 KB Output is correct
18 Correct 60 ms 9584 KB Output is correct
19 Correct 192 ms 31372 KB Output is correct
20 Correct 934 ms 50388 KB Output is correct
21 Correct 422 ms 35372 KB Output is correct
22 Correct 171 ms 35780 KB Output is correct
23 Correct 906 ms 50440 KB Output is correct
24 Correct 914 ms 50360 KB Output is correct
25 Correct 893 ms 50388 KB Output is correct
26 Correct 185 ms 31152 KB Output is correct
27 Correct 234 ms 31248 KB Output is correct
28 Correct 196 ms 31104 KB Output is correct
29 Correct 195 ms 31276 KB Output is correct
30 Correct 192 ms 31372 KB Output is correct
31 Correct 6 ms 5112 KB Output is correct
32 Correct 6 ms 5116 KB Output is correct
33 Correct 6 ms 5112 KB Output is correct
34 Correct 6 ms 5112 KB Output is correct
35 Correct 6 ms 5112 KB Output is correct
36 Correct 6 ms 5112 KB Output is correct
37 Correct 6 ms 5112 KB Output is correct
38 Correct 6 ms 5112 KB Output is correct
39 Correct 6 ms 5112 KB Output is correct
40 Correct 6 ms 5112 KB Output is correct
41 Correct 340 ms 28328 KB Output is correct
42 Correct 776 ms 43604 KB Output is correct
43 Correct 781 ms 43860 KB Output is correct
44 Correct 184 ms 32376 KB Output is correct
45 Correct 856 ms 43596 KB Output is correct
46 Correct 843 ms 43604 KB Output is correct
47 Correct 801 ms 43548 KB Output is correct
48 Correct 753 ms 43736 KB Output is correct
49 Correct 788 ms 43612 KB Output is correct
50 Correct 909 ms 43524 KB Output is correct
51 Correct 791 ms 43688 KB Output is correct
52 Correct 827 ms 43620 KB Output is correct
53 Correct 762 ms 43988 KB Output is correct
54 Correct 781 ms 43756 KB Output is correct
55 Correct 781 ms 43988 KB Output is correct
56 Correct 755 ms 43788 KB Output is correct
57 Correct 775 ms 43628 KB Output is correct
58 Correct 767 ms 43664 KB Output is correct
59 Correct 114 ms 27976 KB Output is correct
60 Correct 758 ms 43728 KB Output is correct
61 Correct 698 ms 44904 KB Output is correct
62 Correct 132 ms 24300 KB Output is correct
63 Correct 144 ms 29868 KB Output is correct
64 Correct 130 ms 24300 KB Output is correct
65 Correct 136 ms 24316 KB Output is correct
66 Correct 161 ms 30576 KB Output is correct
67 Correct 137 ms 34188 KB Output is correct
68 Correct 132 ms 24320 KB Output is correct
69 Correct 133 ms 33312 KB Output is correct
70 Correct 130 ms 24296 KB Output is correct
71 Correct 131 ms 33372 KB Output is correct
72 Correct 498 ms 35152 KB Output is correct
73 Correct 888 ms 50364 KB Output is correct
74 Correct 936 ms 50416 KB Output is correct
75 Correct 922 ms 50372 KB Output is correct
76 Correct 915 ms 50344 KB Output is correct
77 Correct 917 ms 50372 KB Output is correct
78 Correct 1000 ms 50504 KB Output is correct
79 Correct 919 ms 50236 KB Output is correct
80 Correct 877 ms 50368 KB Output is correct
81 Correct 901 ms 50608 KB Output is correct
82 Correct 908 ms 51188 KB Output is correct
83 Correct 919 ms 51304 KB Output is correct
84 Correct 898 ms 51280 KB Output is correct
85 Correct 928 ms 51256 KB Output is correct
86 Correct 1126 ms 51404 KB Output is correct
87 Correct 935 ms 51444 KB Output is correct
88 Correct 885 ms 51260 KB Output is correct
89 Correct 371 ms 35064 KB Output is correct
90 Correct 931 ms 51316 KB Output is correct
91 Correct 858 ms 52268 KB Output is correct
92 Correct 203 ms 31796 KB Output is correct
93 Correct 354 ms 31768 KB Output is correct
94 Correct 202 ms 31716 KB Output is correct
95 Correct 204 ms 31712 KB Output is correct
96 Correct 364 ms 31764 KB Output is correct
97 Correct 396 ms 33968 KB Output is correct
98 Correct 193 ms 31724 KB Output is correct
99 Correct 380 ms 35408 KB Output is correct
100 Correct 201 ms 31968 KB Output is correct