Submission #497062

#	Time	Username	Problem	Language	Result	Execution time	Memory
497062		deinfreund	Valley (BOI19_valley)	C++17	100 / 100	419 ms	81208 KiB

valley

#include <bits/stdc++.h>
#define int int64_t
using namespace std;
 
vector<vector<pair<int, int>>>graph;
vector<vector<int>>up, val;
vector<int>tin, tout, dist, lvl, shh, shop;
 
int timer = 0;
int l = 32;
 
int min(int a, int b){
	if(a < b) return a;
	return b;
}
 
void dfs(int v, int p){
	tin[v] = timer++;
	up[v][0] = p;
 
	if(shop[v]) shh[v] = 0;
	
	for(int i = 1; i<=l; ++i){
		up[v][i] = up[up[v][i-1]][i-1];
	}
	
	for(auto [u, w]: graph[v]){
		if(u != p){
			lvl[u] = lvl[v] + 1;
			dist[u] = dist[v] + w;
			dfs(u, v);
			shh[v] = min(shh[u] + dist[u]-dist[v], shh[v]);
			assert(dist[u] - dist[v] >= 0);
		} 			
	}
	
	tout[v] = timer++;
}
 
void table(int v, int p){
	val[v][0] = dist[v] - dist[p] + shh[p];
	
	for(int i = 1; i<=l; ++i){
		val[v][i] = min(val[v][i-1], val[up[v][i-1]][i-1] + dist[v] - dist[up[v][i-1]]);
		assert(dist[v] - dist[up[v][i-1]] >= 0);
	}
	
	for(auto [u, w]: graph[v]) if(u != p) table(u, v);
	
}
 
int check(int u, int v){
	if(tin[u] <= tin[v] && tout[u] >= tout[v]) return 1;
	return 0;
}
 
int lca(int u, int v){
	if(check(u, v)) return u;
	if(check(v, u)) return v;
	
	for(int i = l; i>=0; --i){
		if(!check(up[u][i], v)) u = up[u][i];
	}
	
	return up[u][0];
}
 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, s, q, e; cin>>n>>s>>q>>e;
	--e;
	
	vector<pair<int, int>>edges;
	
	graph.assign(n, vector<pair<int, int>>());
	up.assign(n, vector<int>(33));
	val.assign(n, vector<int>(33));
	tin.assign(n, 0);
	tout.assign(n, 0);
	dist.assign(n, 0);
	lvl.assign(n, 0);
	shh.assign(n, 1e18);
	shop.assign(n, 0);
	
	for(int i = 0; i<n-1; ++i){
		int a, b, c; cin>>a>>b>>c;
		--a; --b;
		graph[a].push_back({b, c});
		graph[b].push_back({a, c});
		edges.push_back({a, b});
	}
	
	for(int i = 0; i<s; ++i){
		int c; cin>>c;
		--c;
		shop[c] = 1;
	}
	
	dfs(e, e);
	
	//for(auto u: shh) cout<<u<<" ";
	//cout<<endl;
	
	
	table(e, e);
	/*
	for(int i = 0; i<n; ++i){
		for(int j = 0; j<3; ++j) cout<<val[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
	*/
	/*
	for(auto [x, y]: edges) cout<<x<<" "<<y<<endl;
	cout<<endl;
	*/
	
	for(int i = 0; i<q; ++i){
		int j, r; cin>>j>>r;
		--j; --r;
		int a = edges[j].first;
		int b = edges[j].second;
		int cur;
		
		if(lvl[a] > lvl[b]) cur = a;
		else cur = b;
		
		//cout<<cur<<" "<<r<<" "<<j<<endl;
		
		if(lca(cur, r) != cur) cout<<"escaped"<<'\n';
		else{
			
			int one = shh[r];
			int range = lvl[r] - lvl[cur];
			int jump = r;
			int two = 1e18;
			
			for(int i = l; i>=0; --i){
				if(range >= 1ll<<i){
					range -= 1ll<<i;
					two = min(two, val[jump][i] + dist[r] - dist[jump]);
					assert(dist[r] >= dist[jump]); 
					jump = up[jump][i];
					
					//cout<<jump<<" "<<two<<endl;
 
				}
			}
			
			if(min(one, two) < 1e18) cout<<min(one, two)<<'\n';
			else cout<<"oo"<<'\n';			
		}
	}
}

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