Submission #784118

#	Time	Username	Problem	Language	Result	Execution time	Memory
784118		raysh07	Valley (BOI19_valley)	C++17	100 / 100	144 ms	53712 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int n, s, q, r;
const int N = 1e5 + 69;
vector <pair<int, int>> adj[N];
int dp[N], l1[N][20], l2[N][20], tin[N], tout[N], d[N], ok1[N], timer = 0;
bool ok[N];

void dfs(int u, int p){
	dp[u] = INF;
	tin[u] = ++timer;
	if (ok[u]) dp[u] = 0;
	for (auto [v, w] : adj[u]){
		if (v != p){
			l2[v][0] = u;
			d[v] = d[u] + w;
			ok1[v] = ok1[u] + 1;
			dfs(v, u);
			dp[u] = min(dp[u], dp[v] + w);
		}
	}
	tout[u] = timer;
}

void Solve()
{
	cin >> n >> s >> q >> r;

	vector <pair<int, int>> e;

	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});
	}

	while (s--){
		int x; cin >> x;
		ok[x] = true;
	}

	dfs(r, -1);

	for (int i = 1; i <= n; i++){
		l1[i][0] = dp[i];
	}

	for (int j = 1; j < 20; j++){
		for (int i = 1; i <= n; i++){
			l2[i][j] = l2[l2[i][j - 1]][j - 1];
			int x = l2[i][j - 1];
			if (x == 0) continue;

			l1[i][j] = min(l1[i][j - 1], l1[x][j - 1] + d[i] - d[x]);
		}
	}

	while (q--){
		int id, x; cin >> id >> x;

		--id;
		if (d[e[id].first] < d[e[id].second]) swap(e[id].first, e[id].second);

		int u = e[id].first;
		int v = e[id].second;

		if (tin[u] <= tin[x] && tout[u] >= tout[x]){
			int ans = INF;
			int add = 0;

			int lol = ok1[x] - ok1[v];
		//	cout << lol << "\n";

			for (int i = 0; i < 20; i++){
				if (lol >> i & 1){
					ans = min(ans, add + l1[x][i]);
					add += d[x] - d[l2[x][i]];
					x = l2[x][i];
				}
			}

			if (ans == INF) cout << "oo\n";
			else cout << ans << "\n";
		} else {
			cout << "escaped\n";
		}
	}
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;

   // freopen("in",  "r", stdin);
   // freopen("out", "w", stdout);

  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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