Submission #446625

#	Time	Username	Problem	Language	Result	Execution time	Memory
446625		aryan12	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1040 ms	89532 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 4e5 + 5;

struct reach_tree_node {
	int val, par, max_par;
} *rt_node[N * 2];

vector<array<int, 2> > g[N];
vector<array<int, 2> > dist(N);
vector<int> startNodes;
int n, m;
int DP[19][N], depth[N];

int Find(int x) {
	if(rt_node[x]->max_par == x) {
		return x;
	}
	return rt_node[x]->max_par = Find(rt_node[x]->max_par);
}

void Unite(int a, int b, int fakeNodeIdx, int valFeed) {
	a = Find(a), b = Find(b);
	//cout << "a = " << a << ", b = " << b << "\n";
	rt_node[a]->par = fakeNodeIdx;
	rt_node[b]->par = fakeNodeIdx;
	rt_node[a]->max_par = fakeNodeIdx;
	rt_node[b]->max_par = fakeNodeIdx;
	rt_node[fakeNodeIdx]->val = valFeed;
}

void dijkstra() {
	for(int i = 0; i < N; i++) {
		dist[i][0] = 1e15;
		dist[i][1] = i;
	}
	priority_queue<array<int, 2>, vector<array<int, 2> >, greater<array<int, 2> > > pq;
	for(int i = 0; i < startNodes.size(); i++) {
		dist[startNodes[i]][0] = 0;
		pq.push({dist[startNodes[i]][0], startNodes[i]});
	}
	while(!pq.empty()) {
		int cur_dist = pq.top()[0], node = pq.top()[1];
		pq.pop();
		if(cur_dist != dist[node][0]) {
			continue;
		}
		for(int i = 0; i < g[node].size(); i++) {
			if(dist[g[node][i][0]][0] > dist[node][0] + g[node][i][1]) {
				dist[g[node][i][0]][0] = dist[node][0] + g[node][i][1];
				pq.push({dist[g[node][i][0]][0], g[node][i][0]});
			}
		}
	}
}

int LCA(int x, int y) {
	if(depth[x] > depth[y]) {
		swap(x, y);
	}
	int diff = depth[y] - depth[x];
	for(int i = 18; i >= 0; i--) {
		if((1 << i) <= diff) {
			diff -= (1 << i);
			y = DP[i][y];
		}
	}
	if(x == y) {
		return x;
	}
	for(int i = 18; i >= 0; i--) {
		if(DP[i][x] != DP[i][y]) {
			x = DP[i][x];
			y = DP[i][y];
		}
	}
	return DP[0][x];
}

void Solve() {
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	int startLen;
	cin >> startLen;
	for(int i = 0; i < startLen; i++) {
		int node;
		cin >> node;
		startNodes.push_back(node);
	}
	dijkstra();
	/*for(int i = 1; i <= n; i++) {
		cout << dist[i][0] << " ";
	}
	cout << "\n";*/
	for(int i = 1; i <= 2 * n; i++) {
		rt_node[i] = new reach_tree_node();
		rt_node[i]->max_par = i;
		rt_node[i]->par = i;
		rt_node[i]->val = dist[i][0];
	}
	int fakeNode = n + 1;
	bool visited[N];
	for(int i = 0; i < N; i++) {
		visited[i] = false;
	}
	sort(dist.begin() + 1, dist.begin() + 1 + n);
	reverse(dist.begin() + 1, dist.begin() + 1 + n);
	for(int i = 1; i <= n; i++) {
		int node = dist[i][1];
		visited[node] = true;
		for(int j = 0; j < g[node].size(); j++) {
			if(visited[g[node][j][0]]) {
				if(Find(node) == Find(g[node][j][0])) {
					continue;
				}
				Unite(node, g[node][j][0], fakeNode++, dist[i][0]);
				//cout << "node = " << node << ", g[node][j][0] = " << g[node][j][0] << ", fakeNode = " << fakeNode << ", dist[i][0] = " << dist[i][0] << "\n";
				//cout << "Find(node) = " << Find(node) << ", Find(g[node][j][0]) = " << Find(g[node][j][0]) << "\n";
			}
		}
	}
	for(int i = 1; i < fakeNode; i++) {
		DP[0][i] = rt_node[i]->par;
	}
	for(int i = 1; i < 19; i++) {
		for(int j = 1; j < fakeNode; j++) {
			if(DP[i - 1][j] == -1) {
				DP[i][j] = -1;
			}
			else {
				DP[i][j] = DP[i - 1][DP[i - 1][j]];
			}
		}
	}
	depth[fakeNode - 1] = 0;
	for(int i = fakeNode - 2; i > 0; i--) {
		depth[i] = depth[rt_node[i]->par] + 1;
	}
	int q;
	cin >> q;
	while(q--) {
		int s, e;
		cin >> s >> e;
		int lca = LCA(s, e);
		cout << rt_node[lca]->val << "\n";
	}
}

int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void dijkstra()':
plan.cpp:42:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i = 0; i < startNodes.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
plan.cpp:52:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i = 0; i < g[node].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
plan.cpp: In function 'void Solve()':
plan.cpp:120:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   for(int j = 0; j < g[node].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~

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