제출 #1333598

#제출 시각아이디문제언어결과실행 시간메모리
1333598crispxxValley (BOI19_valley)C++20
100 / 100
148 ms47180 KiB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll inf = 1e18;

bool chmin(ll &a, const ll &b) {
	return a > b ? a = b, true : false;
}

void solve() {
	int N, S, Q, E;
	
	cin >> N >> S >> Q >> E;
	
	E--;
	
	vector<vector< array<int, 3> >> adj(N);
	
	for(int i = 0; i < N - 1; i++) {
		int A, B, W; cin >> A >> B >> W;
		
		A--, B--;
		
		adj[A].push_back({B, W, i});
		adj[B].push_back({A, W, i});
	}
	
	vector<int> is_S(N);
	
	for(int i = 0; i < S; i++) {
		int v; cin >> v;
		
		v--;
		
		is_S[v] = 1;
	}
	
	vector jmp(N, vector(20, E));
	vector mno(N, vector(20, inf));
	
	vector<ll> cost(N), mn(N, inf), d(N);
	
	vector<int> ind(N - 1), tin(N), tout(N);
	
	{
		int timer = 0;
		
		auto dfs = [&](auto &&self, int v, int p) -> void {
			if(is_S[v]) mn[v] = cost[v];
			
			tin[v] = ++timer;
			
			for(auto [to, w, i] : adj[v]) {
				if(to == p) continue;
				
				ind[i] = to;
				
				cost[to] = cost[v] + w;
				
				d[to] = d[v] + 1;
				
				self(self, to, v);
				
				chmin(mn[v], mn[to]);
			}
			
			tout[v] = timer;
		};
		
		dfs(dfs, E, E);
	}
	
	{
		auto dfs = [&](auto &&self, int v, int p) -> void {
			jmp[v][0] = p;
			
			if(mn[v] != inf) mno[v][0] = mn[v] - 2 * cost[v];
			
			if(v != p && mn[p] != inf) chmin(mno[v][0], mn[p] - 2 * cost[p]);
			
			for(int i = 1; i < 20; i++) {
				jmp[v][i] = jmp[ jmp[v][i - 1] ][i - 1];
				mno[v][i] = min( mno[v][i - 1], mno[ jmp[v][i - 1] ][i - 1] );
			}
			
			for(auto [to, w, i] : adj[v]) {
				if(to == p) continue;
				
				self(self, to, v);
				
				chmin(mn[v], mn[to]);
			}
		};
		
		dfs(dfs, E, E); 
	}
	
	auto upper = [&](int u, int v) {
		return tin[v] >= tin[u] && tout[v] <= tout[u];
	};
	
	auto kth = [&](int u, int k) {
		ll ans = inf;
		
		if(mn[u] != inf) chmin(ans, mn[u] - 2 * cost[u]);
		
		// cout << "cost: " << cost[u] << '\n';
		
		for(int i = 0; i < 20; i++) {
			if(k >> i & 1) {
				// cout << mno[u][i] << ' ';
				chmin(ans, mno[u][i]);
				u = jmp[u][i];
			}
		}
		
		// cout << '\n';
		
		return ans;
	};
	
	// for(auto &x : ind) cout << x + 1 << ' ';
	// cout << '\n';
	
	while(Q--) {
		int I, R; cin >> I >> R;
		
		I--, R--;
		
		int v = ind[I];
		
		// cout << '\n';
		
		// cout << v + 1 << ' ' << R + 1 << '\n';
		
		if(d[R] < d[v] || !upper(v, R)) {
			cout << "escaped" << '\n';
			continue;
		}
		
		ll ans = kth(R, d[R] - d[v]);
		
		ll res = ans + cost[R];
		
		if(res >= inf) {
			cout << "oo" << '\n';
			continue;
		}
		
		cout << res << '\n';
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...