Submission #705593

#	Time	Username	Problem	Language	Result	Execution time	Memory
705593		bane	Valley (BOI19_valley)	C++17	23 / 100	276 ms	42616 KiB

valley

/*
 * prep: 4.3
 */

#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define ll long long 
#ifdef LOCAL
    #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
    #define eprintf(...) 42
#endif
int n,s,q,e;
vector<pair<int,int>>adj[100002];
pair<int,int>id[100002];
ll shop[100002], dp[100002], depth[100002];
int up[100002][20];
ll dp2[100002][20];
ll nq[100002];
void DepthFirstSearch(int u, int p){
	dp[u] = (ll)1e15;
	dp2[u][0] = (ll)1e15;
	depth[u] = depth[p]+1;
	up[u][0]=(u == e ? e : p);
	if (shop[u])dp[u]=0;
	for (auto edge: adj[u]){
		if (edge.fr == p)continue;
		nq[edge.fr] = nq[u]+edge.sc;
		DepthFirstSearch(edge.fr, u);
		dp[u] = min(dp[u], dp[edge.fr] + edge.sc);
	}
	dp2[u][0] = dp[p] - nq[p];
}

void build(){
	for (int level = 1; level < 20; ++level){
		for (int node = 1; node <= n; ++node){
			up[node][level] = up[up[node][level-1]][level-1];
			dp2[node][level] = min(dp2[node][level - 1], dp2[up[node][level-1]][level-1]);
		}
	}
}
int LowestCommonAncestor(int a, int b){
	if (depth[a] < depth[b])swap(a,b);
	int k = depth[a] -depth[b];
	for (int lvl = 19; lvl >= 0; --lvl){
		if ((1 << lvl) & k){
			a = up[a][lvl];
		}
	}
	if(a == b)return a;
	for (int i = 19; i>=0; --i){
		if(up[a][i] != up[b][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s >> q >> e;
	for (int i = 0; i + 1 < n; i++){
		int a,b,w;cin >> a >> b >> w;
		adj[a].pb(mp(b,w));
		adj[b].pb(mp(a,w));
		id[i] = mp(a,b);
	}
	for (int i= 0; i < s; i++){
		int x; cin >> x;
		shop[x] = 1;
	}
	depth[0]=-1;
	dp[0] = (int)1e9;
	DepthFirstSearch(e,0);
	build();
	for (int i = 0; i < q; i++){
		int blocked, start;
		cin >> blocked >> start;
		if(start==e){cout<<"escaped"<<'\n';continue;}
		int lower = (up[id[blocked-1].fr][0] == id[blocked-1].sc ? id[blocked-1].fr : id[blocked-1].sc);
		//cout<<LowestCommonAncestor(lower, start)<<endl;
		if(LowestCommonAncestor(start, lower) == lower){
			//find minimal shop
			if(shop[start]){
				cout<<0<<endl;
				continue;
			}
			int k = depth[start] - depth[lower];
			int h = nq[start];
			ll ans = (ll)1e15;
			ans = dp[start];
			for (int lvl = 19; lvl >= 0; --lvl){
				if ((1 << lvl) & k){
					ans = min(ans, dp2[start][lvl]);
					start = up[start][lvl];
				}
			}
			if(ans + h >=(ll)1e14)cout<<"oo"<<endl;
			else cout<<ans + h<<'\n';
		}else{
			cout<<"escaped"<<'\n';
		}
	}
	return 0;
}

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