Submission #644397

#	Time	Username	Problem	Language	Result	Execution time	Memory
644397		amoorj	Valley (BOI19_valley)	C++17	100 / 100	322 ms	45208 KiB

valley

//#pragma GCC optimize ("O3,unroll-loops")
//#pragma GCC target ("avx2,bmi,bmi2,popcnt")
#include <bits/stdc++.h>
#define F first
#define pb push_back
#define sz size()
#define S second
using namespace std;
typedef long long int ll;

const int N = 1e5 + 10, LG = 18;
const ll INF = 1e18;
int n,s,q,e,lg2[N],st[N],ft[N],timer = 0;
ll dp[N],h[N],hi[N],val[N],mini[N][LG],up[N][LG];
vector<pair<int,int>> adj[N],edg;
vector<ll> vec;
bool shop[N];

void dfs(int v,int p){
	st[v] = ++timer;
	up[v][0] = p;
	for(int j=1;j<LG;j++)
		up[v][j] = up[up[v][j-1]][j-1];
	if(shop[v])
		dp[v] = 0;
	for(auto x:adj[v]){
		int u = x.F, w = x.S;
		if(u == p)
			continue;
		h[u] = h[v] + w;
		hi[u] = hi[v] + 1;
		dfs(u,v);
		dp[v] = min(dp[v], dp[u] + w);
	}
	ft[v] = ++timer;
}
void dfs2(int v,int p){
	mini[v][0] = min(val[v], val[p]);
	for(int j=1;j<LG;j++)
		mini[v][j] = min(mini[v][j-1], mini[up[v][j-1]][j-1]);
	for(auto x:adj[v]){
		int u = x.F;
		if(u == p)
			continue;
		dfs2(u,v);
	}
}
bool is_anc(int anc,int v){
	return (st[anc] <= st[v] && ft[anc] >= ft[v]);
}
ll minx(int v,int x){
	ll ans = val[v];
	for(int j=LG-1;j>-1;j--){
		if(x >= (1 << j)){
			ans = min(ans, mini[v][j]);
			v = up[v][j];
			x -= (1 << j);
		}
	}
	return ans;
}
inline void init(){
	for(int i=0;i<N;i++){
		dp[i] = INF;
	}
	lg2[1] = 0;
	for(int i=2;i<N;i++)
		lg2[i] = lg2[i/2] + 1;
}
inline void input(){
	cin >> n >> s >> q >> e;
	e--;
	int x,y,w;
	for(int i=0;i<n-1;i++){
		cin >> x >> y >> w;
		x--, y--;
		adj[x].pb({y,w}), adj[y].pb({x,w});
		edg.pb({x,y});
	}
	for(int i=0;i<s;i++){
		cin >> x;
		shop[--x] = 1;
	}
}
inline void solve(){
	int x,y;
	hi[e] = 0, h[e] = 0;
	dfs(e,e);
	for(int i=0;i<n;i++){
		val[i] = dp[i] - h[i];
//		cout << dp[i] << ' ' << h[i] << ' ' << i << endl;
	}
	dfs2(e,e);
/*	for(int i=0;i<n;i++){
		for(int j=0;j<LG;j++){
			if(mini[i][j] > 1e17)
				cout << "INF ";
			else
				cout << mini[i][j] << ' ';
		}
		cout << endl;
	}*/
	while(q--){
		cin >> x >> y; // edge , vertex
		x--, y--;
		int v = edg[x].F, u = edg[x].S;
		if(h[v] < h[u])
			swap(v,u);
		if(!is_anc(v,y)){
			cout << "escaped" << endl;
		}
		else{
			ll ans = minx(y,hi[y]-hi[v]);
//			cout << ans << ' ';
			ans += h[y];
			if(ans > 1e16)
				cout << "oo" << endl;
			else
				cout << ans << endl;
		}
	}
}
int main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	init();
	int queries = 1;
//	cin >> queries;
	while(queries--){
		input();
		solve();
	}
	return 0;
}

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