Submission #1108118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108118		orcslop	Valley (BOI19_valley)	C++17	100 / 100	108 ms	37372 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
#define f first
#define s second

struct Edge{
	int a, b, w; 
}; 

const int N = 1e5 + 5; 

int n, s, q, ex; 
bool shop[N]; 
int depth[N]; 
ll d[N]; 
ll mn[17][N]; 
int up[17][N]; 
vector<Edge> e; 
vector<pair<int, int>> adj[N]; 

void dfs(int u, int v){
	up[0][u] = v; 
	mn[0][u] = (shop[u] ? 0 : 1e18); 
	for(auto x : adj[u]){
		if(x.f == v) continue; 
		d[x.f] = d[u] + x.s; 
		depth[x.f] = depth[u] + 1; 
		dfs(x.f, u); 
		mn[0][u] = min(mn[0][u], mn[0][x.f] + x.s); 
	}
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> s >> q >> ex; ex--; 
    for(int i = 0; i < n - 1; i++){
    	int a, b, w; 
    	cin >> a >> b >> w; a--; b--; 
    	adj[a].push_back({b, w}); 
    	adj[b].push_back({a, w}); 
    	e.push_back({a, b, w}); 
    }
    for(int i = 0; i < s; i++){
    	int x; 
    	cin >> x; x--; 
    	shop[x] = 1; 
    }
    dfs(ex, ex); 
    for(int i = 0; i < n; i++){
    	mn[0][i] -= d[i]; 
    }
    for(int i = 1; i < 17; i++){
    	for(int j = 0; j < n; j++){
    		up[i][j] = up[i - 1][up[i - 1][j]]; 
    		mn[i][j] = min(mn[i - 1][j], mn[i - 1][up[i - 1][j]]); 
    	}
    }
    for(int i = 0; i < n - 1; i++){
    	if(d[e[i].a] > d[e[i].b]){
    		swap(e[i].a, e[i].b); 
    	}
    }
    auto jump = [&](int u, int g) -> int{
    	for(int i = 0; i < 17; i++){
    		if(g & (1 << i)){
    			u = up[i][u]; 
    		}
    	}
    	return u; 
    }; 
    auto get_min = [&](int u, int g) -> ll{
    	ll ret = 1e18; 
    	for(int i = 0; i < 17; i++){
    		if(g & (1 << i)){
    			ret = min(ret, mn[i][u]); 
    			u = up[i][u]; 
    		}
    	}
    	return ret; 
    }; 
    while(q--){
    	int u, v; 
    	cin >> u >> v; u--; v--; 
    	int anc = e[u].b, diff = depth[v] - depth[anc]; 
    	if(diff < 0 || jump(v, diff) != anc){
    		cout << "escaped\n"; 
    	}
    	else {
    		ll val = get_min(v, depth[v] - depth[anc] + 1); 
    		if(val > 1e15) cout << "oo\n"; 
    		else cout << val + d[v] << '\n'; 
    	}
    }
    return 0; 
}

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