Submission #860376

#	Time	Username	Problem	Language	Result	Execution time	Memory
860376		iskhakkutbilim	Valley (BOI19_valley)	C++17	100 / 100	143 ms	57532 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;
int is_shop[N+1], depth_sum[N+1];
int depth[N+1], tin[N+1], tout[N+1];
int timer, la[N*2][LOG + 5] ,up[N+1][LOG+2];
int lg[N*2 + 100], dist_shop[N + 10];
void dfs(int v, int par){
	tin[v] = timer++;
	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);
		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]);
}
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(auto [x, y] : edges){
//		cout << x << ' ' << y << '\n';
//	}
//	cout << "\n" << '\n';
	for(int i = 0;i < s; i++){
		int x; cin >> x;
		is_shop[x] = 1;
	}
	dfs(e, e);
	for(int j = 0;j <= LOG; j++){
		for(int i = 1;i <= N; i++){
			if(j == 0){
				la[i][j] = dist_shop[i] - depth_sum[i];
			}else{
				la[i][j] = min(la[i][j-1], la[up[i][j-1]][j-1]);
			}
		}
	}
	while(q--){
		int idx, v; cin >> idx >> v;
	//	cout << edges[idx].ff << ' ' << edges[idx].ss << '\n';
		//	cout << v << " = " << close(idx) << '\n';
		if(!is_parent(close(idx), v)){
			cout << "escaped";
		}else{
			int k = depth[v] - depth[close(idx)];
			int mn = dist_shop[v], vert = v;
			for(int i = 0;i < LOG; i++){
				if(k & (1<<i)){
					mn = min(mn, la[vert][i] + depth_sum[v]);
					vert = up[vert][i];
				}
			}
			mn = min(mn, la[vert][0] + depth_sum[v]);
		//	cout << k << " = " << mn << '\n';
			if(mn >= (int)1e15) cout << "oo";
			else cout << mn;
		}
		cout << '\n';
	}
	return 0;
}

Compilation message (stderr)

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

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