Submission #860305

#	Time	Username	Problem	Language	Result	Execution time	Memory
860305		iskhakkutbilim	Valley (BOI19_valley)	C++17	23 / 100	126 ms	100544 KiB

valley

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

#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int MAX = 2e17;
const int N = 1e5;
const int LOG = 17;
int n, s, q, e;
vector< pair<int, int> > g[N + 1];
vector< pair<int, int> > edges;
vector<int> shops;
int is_shop[N+1], up[N+1][LOG+2], depth_sum[N+1];
int depth[N+1], tin[N+1], tout[N+1], range[N+1];
int timer, T;
int euler[N * 2 + 100];
int lg[N*2 + 100], dist_shop[N + 10];
int lst[N*2+100];
void dfs(int v, int par){
	tin[v] = timer++;
	range[v] = T;
	lst[v] = T;
	euler[T++] = v;
	up[v][0] = par;
	for(int j = 1;j <= LOG; j++){
		up[v][j] = up[up[v][j-1]][j-1];
	}
	int distance = MAX;
	for(auto [to, w] : g[v]){
		if(to == par) continue;
		depth[to] = depth[v] + 1;
		depth_sum[to] = depth_sum[v] + w;
		dfs(to, v);
		lst[v] = T;
		euler[T++] = v;
		distance = min(distance, dist_shop[to] + w);
	}	
	if(is_shop[v]){
		dist_shop[v] = 0;
	}else{
		dist_shop[v] = distance;
	}
	tout[v] = timer;
}
int is_parent(int par, int v){
	return (tin[par] <= tin[v] && tout[v] <= tout[par]);
}
pair<int, int> sparse[LOG+3][N * 2+10];
int query_rmq(int a, int b) {
	if(a > b) swap(a, b);
	int f = lg[b-a + 1];
	if(a == b) return sparse[f][a].ff;
	return min(sparse[f][a].ff,sparse[f][(b - (1<<f)) < 0 ? 0 : (b - (1<<f))].ff);
}
int min_on_way(int u, int v) {
	if(is_parent(u, v)) swap(u, v);
	return query_rmq(range[u], lst[v]);
}
int can_reach(int v, int u, int closed){
	if(is_parent(closed, v) or is_parent(closed, u)) return 0;
	return 1;
}
/*int distance(int v, int u){
	int LCA = lca(v, u);
	return depth_sum[v] + depth_sum[u] - 2*depth_sum[LCA];
}*/
int close(int idx){
	return (depth[edges[idx].ff] < depth[edges[idx].ss] ? edges[idx].ss : edges[idx].ff);
}
main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> n >> s >> q >> e;
	edges.push_back({-1, -1});
	for(int i = 1;i < n; i++){
		int a, b, w; cin >> a >> b >> w;
		g[a].push_back({b, w});
		g[b].push_back({a, w});
		edges.push_back({a, b});
	}
	for(int i = 0;i < s; i++){
		int x; cin >> x;
		shops.push_back(x);
		is_shop[x] = 1;
	}
	dfs(e, e);
//	cout << "Euler path = ";
	for(int i = 0;i < T; i++){
//		cout << euler[i] << ' ';
		sparse[0][i] = {dist_shop[euler[i]] - depth_sum[euler[i]], euler[i]};
	}
//	cout << '\n';
	int logT = 0;
	while ((1<<logT) < T) logT++;
	for(int f = 0; f < logT; f++){
		for(int i = 0;i + (1<<f) < T; i++){
			sparse[f+1][i] = min(sparse[f][i], sparse[f][i + (1<<f)]);
		}
	}
	lg[0] = 0;
	for(int i = 2;i < T; i++){
		lg[i] = lg[i / 2] + 1;
	}
	for(int i = 1;i <= n; i++){
		//  - depth_sum[euler[i].ss]
//		cout << i << " = " << dist_shop[i] - depth_sum[euler[i]] << '\n';
	}
//	cout << '\n';
	while(q--){
		int idx, v; cin >> idx >> v;
		if(can_reach(v, e, close(idx))){
			cout << "escaped";
		}else if(s == n){
			cout << 0;
		}else{
			int mn = min_on_way(v, close(idx));
//			cout << range[v] << " " << lst[close(idx)] << " = " << mn << '\n';
//			cout << v << " " << close(idx) << " == " << mn << '\n';
			mn+= depth_sum[v];
			mn = min(mn, dist_shop[v]);
			if(mn >= (int)1e15) cout << "oo";
			else cout << mn;
		}
		cout << '\n';
	}
	return 0;
}

Compilation message (stderr)

valley.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main(){
      | ^~~~

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