Submission #761553

#	Time	Username	Problem	Language	Result	Execution time	Memory
761553		MetalPower	Valley (BOI19_valley)	C++14	100 / 100	196 ms	51936 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll MX = 1e5 + 10;
const ll LG = 19;
const ll INF = 1e18 + 7;

ll N, S, Q, E, dep[MX], in[MX], out[MX], tim = 0;
ll isShop[MX], dist[MX], sp[MX][LG], wt[MX][LG];
vector<pii> adj[MX];

void chmin(ll& a, ll b){
	if(b < a) a = b;
}

void dfs(ll u, ll v){
	in[u] = ++tim;
	if(isShop[u]) dist[u] = 0;
	for(pii nxt : adj[u]){
		if(nxt.fi == v) continue;
		dep[nxt.fi] = dep[u] + nxt.se;
		dfs(nxt.fi, u);
		chmin(dist[u], dist[nxt.fi] + nxt.se);
	}
	out[u] = tim;
}

void dfs2(ll u, ll v){
	if(dist[u] != INF) dist[u] -= dep[u];
	sp[u][0] = v; wt[u][0] = dist[u];
	for(ll j = 1; j < LG; j++){
		sp[u][j] = sp[sp[u][j - 1]][j - 1];
		wt[u][j] = min(wt[u][j - 1], wt[sp[u][j - 1]][j - 1]);
	}
	for(pii nxt : adj[u]){
		if(nxt.fi == v) continue;
		dfs2(nxt.fi, u);
	}
}

void init(){
	for(ll i = 1; i <= N; i++) dist[i] = INF;
	for(ll j = 0; j < LG; j++) sp[0][j] = 0, wt[0][j] = INF;
}

vector<pii> edges;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> S >> Q >> E;
	for(ll i = 1; i < N; i++){
		ll u, v, w; cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		edges.push_back({u, v});
	}

	for(ll i = 1; i <= S; i++){
		ll C; cin >> C;
		isShop[C] = true;
	}

	init();
	dfs(E, 0);
	dfs2(E, 0);

	for(ll i = 0; i < Q; i++){
		ll I, R, tp, lw; cin >> I >> R; I--;
		if(dep[edges[I].fi] < dep[edges[I].se]) tp = edges[I].fi, lw = edges[I].se;
		else tp = edges[I].se, lw = edges[I].fi;

		if(in[lw] <= in[R] && in[R] <= out[lw]){ // contained

			ll curr = R, ans = INF;
			for(ll j = LG - 1; j >= 0; j--){
				if(dep[sp[curr][j]] > dep[lw]){
					chmin(ans, wt[curr][j]);
					curr = sp[curr][j];
				}
			}

			chmin(ans, wt[curr][0]);
			curr = sp[curr][0];
			chmin(ans, dist[lw]);

			if(ans == INF) cout << "oo\n";
			else cout << dep[R] + ans << '\n';

		}else{
			cout << "escaped\n";
		}
	}
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:74:12: warning: variable 'tp' set but not used [-Wunused-but-set-variable]
   74 |   ll I, R, tp, lw; cin >> I >> R; I--;
      |            ^~

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