Submission #1303875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303875		Nonoze	Valley (BOI19_valley)	C++20	100 / 100	298 ms	70696 KiB

valley

/*
*	Author: Nonoze
*	Created: Saturday 20/12/2025
*/
#include <bits/stdc++.h>
using namespace std;

#ifndef DEBUG
	#define dbg(...)
#endif

// #define cout cerr << "OUT: "
#define endl '\n'
#define endlfl '\n' << flush
#define quit(x) return (void)(cout << x << endl)

template<typename T> void read(T& x) { cin >> x; }
template<typename T1, typename T2> void read(pair<T1, T2>& p) { read(p.first), read(p.second); }
template<typename T> void read(vector<T>& v) { for (auto& x : v) read(x); }
template<typename T1, typename T2> void read(T1& x, T2& y) { read(x), read(y); }
template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z) { read(x), read(y), read(z); }
template<typename T1, typename T2, typename T3, typename T4> void read(T1& x, T2& y, T3& z, T4& zz) { read(x), read(y), read(z), read(zz); }
template<typename T> void print(vector<T>& v) { for (auto& x : v) cout << x << ' '; cout << endl; }

#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(v) sort(all(v)), v.erase(unique(all(v)), (v).end())
#define pb push_back
#define mp(a, b) make_pair(a, b)
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define QYES quit("YES")
#define QNO quit("NO")

#define int long long
#define double long double
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=18;



void solve();

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	// cin >> tt;
	while(tt--) solve();
	return 0;
}




int n, k, s, q;
vector<int> depth, nearest;
vector<vector<int>> up, dist, best;
vector<vector<pair<int, int>>> adj;
vector<pair<int, int>> edges;

int dfs(int u, int p) {
	for (auto [v, w]: adj[u]) if (v!=p) {
		depth[v] = depth[u]+1;
		up[v][0] = u;
		dist[v][0]=w;
		for (int i=1; i<LOG; i++) {
			up[v][i] = up[up[v][i-1]][i-1];
			dist[v][i] = dist[v][i-1]+dist[up[v][i-1]][i-1];
		}
		cmin(nearest[u], dfs(v, u));
	}
	return nearest[u]+dist[u][0];
}


void dfs2(int u, int p) {
	for (auto [v, w]: adj[u]) if (v!=p) {
		best[v][0]=nearest[u]+w;
		for (int i=1; i<LOG; i++) best[v][i]=min(best[v][i-1], best[up[v][i-1]][i-1]+dist[v][i-1]);
		dfs2(v, u);
	}
}


void solve() {
	read(n, k, q, s); s--;
	adj.clear(); adj.resize(n);
	for (int i=0; i<n-1; i++) {
		int u, v, w; read(u, v, w); u--, v--;
		adj[u].pb({v, w});
		adj[v].pb({u, w});
		edges.pb({u, v});
	}
	nearest.clear(); nearest.resize(n, inf);
	for (int i=0; i<k; i++) {
		int shop; read(shop); shop--;
		nearest[shop]=0;
	}
	depth.clear(); depth.resize(n, 0);
	up.clear(); up.resize(n, vector<int>(LOG, s));
	dist.clear(); dist.resize(n, vector<int>(LOG, 0));
	best.clear(); best.resize(n, vector<int>(LOG, inf));
	dfs(s, -1);
	dfs2(s, -1);

	while (q--) {
		int i, u; read(i, u); i--, u--;
		int root=(depth[edges[i].fi]>depth[edges[i].se])?edges[i].fi:edges[i].se;
		if (depth[u]<depth[root]) {
			cout << "escaped" << endl;
			continue;
		} else {
			int temp=u;
			for (int j=LOG-1; j>=0; j--) {
				if (depth[up[temp][j]]>=depth[root]) temp=up[temp][j];
			}
			if (temp!=root) {
				cout << "escaped" << endl;
				continue;
			}
		}
		int ans=nearest[u], plus=0;
		for (int j=LOG-1; j>=0; j--) {
			if (depth[up[u][j]]>=depth[root]) {
				cmin(ans, best[u][j]+plus);
				plus+=dist[u][j];
				u=up[u][j];
			}
		}
		if (ans==inf) cout << "oo" << endl;
		else cout << ans << endl;
	}
}

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