Submission #1313443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313443		muhammad-ahmad	Valley (BOI19_valley)	C++20	100 / 100	246 ms	49136 KiB

valley

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;

void fast_io() {
	// freopen("", "r", stdin);
	// freopen("", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie();
	cout.tie();
	cout << setprecision(9);
}

#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second

const int N = 1e5 + 5, L = 17;

vector<pair<int, int>> adj[N];
bool V[N];
vector<int> ord;
int dist[N], dpth[N], Shop[N], par[N], sp[N][L], mi[N][L], magic[N];
int St[N], En[N], Time;
 
void sp_table(int u){
	sp[u][0] = par[u];
	mi[u][0] = magic[u];
	int power = 1;
	for (int i = 1; i < 17; i++){
		power *= 2;
		if (dpth[u] < power){
			sp[u][i] = 0;
			mi[u][i] = 1e18;
		}
		else {
			sp[u][i] = sp[sp[u][i - 1]][i - 1];
			mi[u][i] = min(mi[u][i - 1], mi[sp[u][i - 1]][i - 1]); 
		}
	}
}
 
void dfs(int u){
    St[u] = ++Time;
    ord.push_back(u);

    Shop[u] = (V[u] ? dist[u] : (int)1e18);

    for (auto [v, w] : adj[u]){
        if (v == par[u]) continue;

        par[v] = u;
        dist[v] = dist[u] + w;
        dpth[v] = dpth[u] + 1;

        dfs(v);
        Shop[u] = min(Shop[u], Shop[v]);
    }

    En[u] = Time;
    magic[u] = Shop[u] - 2 * dist[u];
}


void solve() {
	int n, s, q, e;
	cin >> n >> s >> q >> e;
	vector<pair<int, int>> E = {{0, 0}};
	for (int i = 1; i < n; i++){
		int u, v, w; cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		E.push_back({u, v});
	}
	for (int i = 1; i <= s; i++){
		int CC; cin >> CC;
		V[CC] = 1;
	}
	dfs(e);
	
	for (auto i : ord){
		sp_table(i);
	}
	
	for (int Q = 1; Q <= q; Q++){
		int I, R; cin >> I >> R;
		int u = E[I].fi, v = E[I].se;
		int p = (par[v] == u ? v : u);
		if (!(St[p] <= St[R] && St[R] <= En[p])){
			cout << "escaped" << endl;
			continue;
		}
		else if (Shop[p] >= 1e18){
			cout << "oo" << endl;
			continue;
		}
		int diff = dpth[R] - dpth[p];
		int ans = 1e18;
		int po = 0;
		int cur = R;
		while (diff > 0){
			if (diff & 1){
				ans = min(ans, mi[cur][po]);
				cur = sp[cur][po];
			}
			po++;
			diff >>= 1;
		}
		ans = min(ans, magic[p]);
		cout << ans + dist[R] << endl;
	}
	
}

signed main() {
	fast_io();
	srand(chrono::steady_clock::now().time_since_epoch().count());
	int tc = 1;
	// cin >> tc;
	while (tc--) solve();
	return 0;
}

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