Submission #504005

#	Time	Username	Problem	Language	Result	Execution time	Memory
504005		Meloric	Valley (BOI19_valley)	C++17	100 / 100	357 ms	69912 KiB

valley

#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()

using namespace std;

const int inf  = 1e18;

int n, s, q, root;

int timer = 0;

struct edge{
	int id, v, w;
};

vector<vector<edge>> g;
vector<int> shops, down, lvl, val, mp, pre, pst;
vector<vector<int>> up, mn;

void p(vector<int>& A){
	for(auto e : A)cout << e << ' ';
	cout << '\n';
}

void dfs1(int u, int p){
	for(auto [id, v, w] : g[u]){
		if(v == p)continue;
		mp[id] = v;
		lvl[v] = lvl[u] + w;
		dfs1(v, u);
	}
	if(shops[u])down[u] = 0;
	for(auto [id, v, w] : g[u]){
		if(v == p)continue;
		down[u] = min(down[u], down[v] + w);
	}
	val[u] = down[u] - lvl[u];
}

void dfs2(int u, int p){
	pre[u] = timer++;
	up[0][u] = p;
	mn[0][u] = min(val[u], val[up[0][u]]);
	for(int i = 1; i< 30; i++){
		up[i][u] = up[i-1][up[i-1][u]];
		mn[i][u] = min(mn[i-1][u], mn[i-1][up[i-1][u]]);
	}
	for(auto [id, v, w] : g[u]){
		if(v == p)continue;
		dfs2(v, u);
	}
	pst[u] = timer++;
}

int is_anc(int u, int a){
	return pre[u] >= pre[a] && pst[u] <= pst[a];
}

	
void solve(){
	cin >> n >> s >> q >> root; root--;
	mp.assign(n-1, 0);
	g.assign(n, vector<edge>());
	shops.assign(n, 0);
	down.assign(n, inf);
	lvl.assign(n, 0);
	val.assign(n, 0);
	pre.assign(n, 0);
	pst.assign(n, 0);
	
	up.assign(30, vector<int>(n));
	mn.assign(30, vector<int>(n, inf));
	
	for(int i = 0; i< n-1; i++){
		int a, b, w; cin >> a >> b >> w; a--; b--;
		g[a].pb({i, b, w});
		g[b].pb({i, a, w});
	}
	for(int i = 0; i< s; i++){
		int c; cin >> c; c--;
		shops[c] = 1;
	}
	dfs1(root, root);
	dfs2(root, root);
	
	//p(mp); p(pre); p(pst);
	
	for(int i = 0; i< q; i++){
		int id, r; cin >> id >> r; id--; r--;
		//cerr << "NODE: " << mp[id] << '\n';
		if(!is_anc(r, mp[id])){
			cout << "escaped\n";
			continue;
		}
		int start = r;
		int ans = val[r];
		for(int j = 29; j>= 0; j--){
			if(is_anc(up[j][r], mp[id])){
				ans = min(ans, mn[j][r]);
				r = up[j][r];
			}
		}
		ans += lvl[start];
		if(ans == 1e18){
			cout << "oo\n";
			continue;
		}else{
			cout << ans << '\n';
		}
	}
}

		
	
	
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t = 1;
	//cin >> t;
	while(t--)solve();
}

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