Submission #1117187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117187		xnqs	Valley (BOI19_valley)	C++17	100 / 100	98 ms	39056 KiB

valley

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

int gs, sh, q, dest;
std::vector<std::vector<std::pair<int,int>>> adj_list;
std::vector<std::tuple<int,int,int>> edges;
bool is_shop[100005];
std::vector<int> shops;

int tin[100005];
int tout[100005];
int depth[100005];
int64_t dist[100005];
int64_t best_root_path[100005];
int up[17][100005];
int64_t dp[17][100005];

void dfs1(int k, int p, int& timer) {
	tin[k] = tout[k] = ++timer;
	depth[k] = depth[p]+1;
	up[0][k] = p;
	best_root_path[k] = ((is_shop[k]) ? dist[k] : 0x3f3f3f3f3f3f3f3f);
	for (const auto& [i, w] : adj_list[k]) {
		if (i!=p) {
			dist[i] = dist[k]+w;
			dfs1(i,k,timer);
			best_root_path[k] = std::min(best_root_path[k], best_root_path[i]);
			tout[k] = ++timer;
		}
	}
}

void preprocess_binary_lifting() {
	for (int l = 1; l < 17; l++) {
		for (int i = 1; i <= gs; i++) {
			up[l][i] = up[l-1][up[l-1][i]];
			dp[l][i] = std::min(dp[l-1][i], dp[l-1][up[l-1][i]]);
		}
	}
}

int64_t path_min(int a, int b) {
	if (depth[a]>depth[b]) {
		std::swap(a,b);
	}

	int64_t ret = 0x3f3f3f3f3f3f3f3f;
	int diff = depth[b]-depth[a];
	while (diff) {
		int l = 31-__builtin_clz(diff);
		ret = std::min(ret, dp[l][b]);
		b = up[l][b];
		diff ^= (1<<l);
	}

	for (int l = 16; a!=b;) {
		while (l-1>=0&&up[l][a]==up[l][b]) {
			--l;
		}

		ret = std::min(ret, dp[l][a]);
		ret = std::min(ret, dp[l][b]);
		a = up[l][a];
		b = up[l][b];
	}

	return ret;
}

inline bool inside(int a, int b) {
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> gs >> sh >> q >> dest;
	adj_list.resize(gs+1);
	for (int i = 0, a, b, c; i < gs-1; i++) {
		std::cin >> a >> b >> c;
		adj_list[a].emplace_back(b,c);
		adj_list[b].emplace_back(a,c);
		edges.emplace_back(a,b,c);
	}

	shops.reserve(sh);
	for (int i = 0, tmp; i < sh; i++) {
		std::cin >> tmp;
		is_shop[tmp] = 1;
		shops.emplace_back(tmp);
	}

	{ int timer = 0; dfs1(dest,0,timer); }
	for (int i = 1; i <= gs; i++) {
		dp[0][i] = best_root_path[i] - 2*dist[i];
	}
	preprocess_binary_lifting();

	for (auto& [a, b, c] : edges) {
		if (depth[a]>depth[b]) {
			std::swap(a,b);
		}
	}

	while (q--) {
		int edge_idx, node;
		std::cin >> edge_idx >> node;
		--edge_idx;

		if (!(inside(std::get<1>(edges[edge_idx]),dest)^inside(std::get<1>(edges[edge_idx]),node))) {
			std::cout << "escaped\n";
		}
		else {
			if (best_root_path[std::get<1>(edges[edge_idx])]==0x3f3f3f3f3f3f3f3f) {
				std::cout << "oo\n";
			}
			else {
				int64_t ans = dist[node] + path_min(std::get<0>(edges[edge_idx]),node);
				std::cout << ans << "\n";
			}
		}
	}
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41