Submission #860275

#	Time	Username	Problem	Language	Result	Execution time	Memory
860275		iskhakkutbilim	Valley (BOI19_valley)	C++17	59 / 100	3043 ms	102592 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 N = 1e5;
const int LOG = 17;
int n, s, q, e;
const int SQRT = 550;
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;
pair<int, int> euler[N * 2 + 100];
int lg[N*2 + 100];


void dfs(int v, int par){
	tin[v] = timer++;
	range[v] = T;
	euler[T++] = {depth[v], v};
	up[v][0] = par;
	for(int j = 1;j <= LOG; j++){
		up[v][j] = up[up[v][j-1]][j-1];
	}
	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);
		euler[T++] = {depth[v], v};
	}	
	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];


pair<int, int> query_rmq(int a, int b) {
	int f = lg[b-a];
	return min(sparse[f][a], sparse[f][b - (1<<f)]);
}
int lca(int u, int v) {
  return query_rmq(min(range[u], range[v]), max(range[u], range[v]) + 1).ss;
}
int can_reach(int v, int u, int closed){
	int LCA = lca(v, u);
	if(is_parent(closed, LCA)){
		return 1;
	}
	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);
}
int mn;
void calc_dist_shop(int v, int par, int closed, int sm){
	if(is_shop[v]){
		mn = min(mn, sm);
	}
	set<pair<int, int> > st;
	st.insert({0LL, v});
	
	for(auto [to, w] : g[v]){
		if(to == edges[closed].ff and v == edges[closed].ss) continue;
		if(v == edges[closed].ff and to == edges[closed].ss) continue;
		if(to == par) continue;
		calc_dist_shop(to, v, closed, sm + w);
	}
}


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(1, 1);
	for(int i = 0;i < T; i++){
		sparse[0][i] = euler[i];
	}
	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] = -1;
	for(int i = 1;i < T; i++){
		lg[i] = lg[i / 2] + 1;
	}
	while(q--){
		int idx, v; cin >> idx >> v;
		if(can_reach(v, e, close(idx))){
			cout << "escaped";
		}else if(s == n){
			cout << 0;
		}else{
			mn = LLONG_MAX;
			if(shops.size() > SQRT){
				for(int sh : shops){
					if(can_reach(v, sh, close(idx)))
					mn = min(mn, distance(v, sh));
				}
			}else{
				calc_dist_shop(v, v, idx, 0);
			}
			if(mn == LLONG_MAX) cout << "oo";
			else cout << mn;
		}
		cout << '\n';
	}
	return 0;
}

Compilation message (stderr)

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

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