Submission #1117142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117142		xnqs	Valley (BOI19_valley)	C++17	32 / 100	2208 ms	165576 KiB

valley

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <tuple>
#include <set>
#include <functional>
 
enum QueryAnswer {
	AnswerEscaped = -2,
	AnswerInfinity = -1,
};
 
int gs, sh, q, dest;
std::vector<int> shops;
bool is_shop[100005];
std::vector<std::vector<std::pair<int,int>>> adj_list;
std::vector<std::tuple<int,int,int>> edges;
std::vector<std::pair<int,int>> queries[100005];
int64_t query_ans[100005];
 
int depth[100005];
int64_t dist[100005];
int par[100005];
int sp_tb_tour[18][200005];
int tin[100005];
int tout[100005];
 
int fnwk[200005];
 
void fnwk_add(int k, int val) {
	while (k < 200005) {
		fnwk[k] += val;
		k += k&-k;
	}
}
 
int fnwk_query(int pos) {
	int ret = 0;
	while (pos > 0) {
		ret += fnwk[pos];
		pos ^= pos&-pos;
	}
	return ret;
}
 
inline int fnwk_query(int l, int r) {
	return fnwk_query(r) - fnwk_query(l-1);
}
 
int dcmp_root;
std::vector<std::vector<int>> adj_list_dcmp;
std::set<std::pair<int64_t,int>> benis_in[100005]; // inside of subtree
std::set<std::pair<int64_t,int>> benis_out[100005]; // outside of subtree
int par_dcmp[100005];
 
inline int highest_node(int a, int b) {
	return ((depth[a]<=depth[b]) ? a : b);
}
 
void dfs1(int k, int p, int& timer) {
	depth[k] = depth[p]+1;
	par[k] = p;
	
	++timer;
	sp_tb_tour[0][timer] = k;
	tin[k] = tout[k] = timer;
 
	for (const auto& [i, w] : adj_list[k]) {
		if (i!=p) {
			dist[i] = dist[k]+w;
			dfs1(i,k,timer);
			++timer;
			sp_tb_tour[0][timer] = k;
			tout[k] = timer;
		}
	}
}
 
void build_sparse_table() {
	for (int l = 1; l < 18; l++) {
		for (int i = 1; i+(1<<l)-1 <= 2*gs-1; i++) {
			sp_tb_tour[l][i] = highest_node(sp_tb_tour[l-1][i],sp_tb_tour[l-1][i+(1<<(l-1))]);
		}
	}
}
 
inline int get_lca(int a, int b) {
	int l = tin[a];
	int r = tin[b];
	if (l>r) {
		std::swap(l,r);
	}
 
	int lvl = 31-__builtin_clz(r-l+1);
	return highest_node(sp_tb_tour[lvl][l],sp_tb_tour[lvl][r-(1<<lvl)+1]);
}
 
inline int64_t get_dist(int a, int b) {
	if (!a||!b) {
		return 0x3f3f3f3f3f3f3f3f;
	}
	return dist[a] + dist[b] - 2*dist[get_lca(a,b)];
}
 
void build_centroid_decomp() {
	std::vector<int> sub_sz(gs+1,0);
	std::vector<bool> blocked(gs+1,0);
 
	const std::function<int(int,int)> dfs_sz = [&](int k, int p) {
		sub_sz[k] = 1;
		for (const auto& [i, w] : adj_list[k]) {
			if (!blocked[i]&&i!=p) {
				sub_sz[k] += dfs_sz(i,k);
			}
		}
		return sub_sz[k];
	};
 
	const std::function<int(int,int,int)> dfs_centroid = [&](int k, int p, int sz) {
		for (const auto& [i, w] : adj_list[k]) {
			if (i!=p&&!blocked[i]&&sub_sz[i]>sz/2) {
				return dfs_centroid(i,k,sz);
			}
		}
		return k;
	};
 
	const std::function<void(int,int)> dfs_build = [&](int k, int p) {
		int sz = dfs_sz(k,0);
		int cen = dfs_centroid(k,0,sz);
 
		if (p) {
			//std::cout << p << " " << cen << "\n";
			adj_list_dcmp[p].emplace_back(cen);
			adj_list_dcmp[cen].emplace_back(p);
			par_dcmp[cen] = p;
		}
		else {
			dcmp_root = cen;
			//std::cout << dcmp_root << "\n";
		}
 
		blocked[cen] = 1;
		for (const auto& [i, w] : adj_list[cen]) {
			if (!blocked[i]) {
				dfs_build(i,cen);
			}
		}
	};
 
	dfs_build(1,0);
}
 
void decomp_add(std::set<std::pair<int64_t,int>>* benis, int node) {
	int k = node;
	while (k) {
		benis[k].emplace(get_dist(node,k), node);
		k = par_dcmp[k];
	}
}
 
void decomp_remove(std::set<std::pair<int64_t,int>>* benis, int node) {
	int k = node;
	while (k) {
		benis[k].erase(benis[k].lower_bound(std::pair<int64_t,int>(get_dist(node,k), node)));
		k = par_dcmp[k];
	}
}
 
int64_t decomp_query(std::set<std::pair<int64_t,int>>* benis, int node, int sub_root, int mode) {
	int k = node;
	int64_t ret = 0x3f3f3f3f3f3f3f3f;
	while (k) {
		for (const auto& [a, b] : benis[k]) {
			// the most dogshit "optimization" but its all i can think of
			if (mode^(tin[sub_root] <= tin[node] && tout[node] <= tout[sub_root])) {
				ret = std::min(ret, a + get_dist(node,k));
				break;
			}
		}
		k = par_dcmp[k];
	}
	return ret;
}
 
void dfs_solve(int k, int p) {
	for (const auto& [node, qidx] : queries[k]) {
		//std::cout << k << " " << node << " " << qidx << "\n";
		if (tin[k]<=tin[node]&&tout[node]<=tout[k]) {
			query_ans[qidx] = decomp_query(benis_in, node, k, 0);
		}
		else {
			query_ans[qidx] = decomp_query(benis_out, node, k, 1);
		}
		if (is_shop[node]) {
			query_ans[qidx] = 0;
		}
	}
 
	if (is_shop[k]) {
		decomp_remove(benis_in, k);
		decomp_add(benis_out, k);
	}
	for (const auto& [i, w] : adj_list[k]) {
		if (i!=p) {
			dfs_solve(i,k);
		}
	}
	if (is_shop[k]) {
		decomp_remove(benis_out, k);
		decomp_add(benis_in, k);
	}
}
 
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);
	adj_list_dcmp.resize(gs+1);
	edges.reserve(gs-1);
 
	for (int i = 0, a, b, c; i < gs-1; i++) {
		std::cin >> a >> b >> c;
		edges.emplace_back(a,b,c);
		adj_list[a].emplace_back(b,c);
		adj_list[b].emplace_back(a,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(1,0,timer); }
	build_sparse_table();
	for (auto& [a, b, c] : edges) {
		if (depth[a]>depth[b]) {
			std::swap(a,b);
		}
	}
 
	/*for (int i = 1; i <= gs; i++) {
		std::cout << i << " " << tin[i] << " " << tout[i] << "\n";
	}*/
 
	build_centroid_decomp();
 
	for (int i = 1; i <= gs; i++) {
		benis_in[i].emplace(0x3f3f3f3f3f3f3f3f,0);
		benis_out[i].emplace(0x3f3f3f3f3f3f3f3f,0);
	}
 
	for (const auto& i : shops) {
		fnwk_add(tin[i],1);
	}
 
	for (int i = 0, edge_idx, node; i < q; i++) {
		std::cin >> edge_idx >> node; --edge_idx;
 
		//queries[std::get<1>(edges[edge_idx])].emplace_back(node, i);
 
		//std::cout << i << " " << edge_idx << " " << std::get<0>(edges[edge_idx]) << " " << std::get<1>(edges[edge_idx]) << " " << node << "\n";
		if (tin[std::get<1>(edges[edge_idx])] <= tin[node] && tout[node] <= tout[std::get<1>(edges[edge_idx])]) {
			if (tin[std::get<1>(edges[edge_idx])] <= tin[dest] && tout[dest] <= tout[std::get<1>(edges[edge_idx])]) {
				query_ans[i] = AnswerEscaped;
			}
			else if (!fnwk_query(tin[std::get<1>(edges[edge_idx])], tout[std::get<1>(edges[edge_idx])])) {
				query_ans[i] = AnswerInfinity;
			}
			else {
				queries[std::get<1>(edges[edge_idx])].emplace_back(node, i);
			}
		}
		else {
			if (!(tin[std::get<1>(edges[edge_idx])] <= tin[dest] && tout[dest] <= tout[std::get<1>(edges[edge_idx])])) {
				query_ans[i] = AnswerEscaped;
			}
			else if (!fnwk_query(1, tin[std::get<1>(edges[edge_idx])]) && !fnwk_query(tout[std::get<1>(edges[edge_idx])], 2*gs-1)) {
				query_ans[i] = AnswerInfinity;
			}
			else {
				queries[std::get<1>(edges[edge_idx])].emplace_back(node, i);
			}
		}
	}
 
	for (int i = 1; i <= gs; i++) {
		if (is_shop[i]) {
			decomp_add(benis_in,i);
		}
	}
	dfs_solve(1,0);
 
	/*for (int i = 1; i <= gs; i++) {
		std::cout << i << "\n";
		for (const auto& [a, b] : benis_in[i]) {
			std::cout << a << " " << b << "\n";
		}
		std::cout << "\n";
	}*/
 
	for (int i = 0; i < q; i++) {
		if (query_ans[i]==AnswerEscaped) {
			std::cout << "escaped\n";
		}
		else if (query_ans[i]==AnswerInfinity||query_ans[i]>=0x3f3f3f3f3f3f3f3f) {
			std::cout << "oo\n";
		}
		else {
			std::cout << query_ans[i] << "\n";
		}
	}
}

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