Submission #567473

#	Time	Username	Problem	Language	Result	Execution time	Memory
567473		_karan_gandhi	Valley (BOI19_valley)	C++17	100 / 100	314 ms	60176 KiB

valley

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

#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
#define ll long long

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }

vector<vector<pair<int, int>>> adj;
vector<int> tin, tout, par, dep;
vector<ll int> dist, dp1, dp2;
vector<bool> shop;
int timer = 0;

void dfs(int u, int p, ll int dis, int d = 0) {
	dist[u] = dis;
	tin[u] = timer++;
	par[u] = p;
	dep[u] = d;

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

		dfs(v, u, dis + w, d + 1);
	}

	if (shop[u]) dp1[u] = dist[u];
	else dp1[u] = 1e18;

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

		dp1[u] = min(dp1[u], dp1[v]);
	}

	tout[u] = timer - 1;
}

bool is_acc(int acc, int child) {
	if (acc == child) return 1;
	return tin[acc] < tin[child] && tin[child] <= tout[acc];
}

void solve() {
	int n, s, q, e; cin >> n >> s >> q >> e;

	adj.resize(n);
	dp1.resize(n);
	dp2.resize(n);
	tin.resize(n);
	tout.resize(n);
	dist.resize(n);
	shop.resize(n);
	par.resize(n);
	dep.resize(n);

	fill(all(dp1), 1e18);

	vector<pair<pair<int, int>, int>> edges;

	for (int i = 0; i < n - 1; i++) {
		int a, b; cin >> a >> b;
		int c; cin >> c;
		a--, b--;

		adj[a].emplace_back(b, c);
		adj[b].emplace_back(a, c);
		edges.emplace_back(make_pair(a, b), c);
	}

	for (int i = 0; i < s; i++) {
		int a; cin >> a;
		shop[a - 1] = 1;
	}

	// e is the root
	dfs(e - 1, e - 1, 0);
	for (int i = 0; i < n; i++) {
		dp1[i] = dp1[i] - 2 * dist[i];
	}

	// eureka!! binary lifting for path queries
	const int LOG = 20;
	vector<vector<ll int>> jumpNode(n, vector<ll int>(20)), jumpDP(n, vector<ll int>(20));

	for (int i = 0; i < n; i++) {
		jumpNode[i][0] = par[i];
		jumpDP[i][0] = dp1[i];
	}

	for (int i = 1; i < LOG; i++) {
		for (int j = 0; j < n; j++) {
			jumpNode[j][i] = jumpNode[jumpNode[j][i - 1]][i - 1];
			jumpDP[j][i] = min(jumpDP[j][i - 1], jumpDP[jumpNode[j][i - 1]][i - 1]); // somewhat like sparse tables
		}
	}

	// cout << jumpDP << endl;

	auto query = [&](int u, int k) -> ll int {
		int pow = LOG;
		ll int res = 1e18;
		// cout << pl(k) << pl(u) << endl;
		// cout << pl(jumpDP[u][0]) << endl;
		while (k > 0) {
			while (k < (1 << pow)) pow--;
			res = min(res, jumpDP[u][pow]);
			// cout << pl(jumpDP[u][pow]) << endl;
			u = jumpNode[u][pow];
			k -= (1 << pow);
		}

		return res;
	};

	while (q--) {
		int a, b; cin >> a >> b;

		a--, b--;
		pair<int, int> edge = edges[a].first;
		if (is_acc(edge.first, b) && is_acc(edge.second, b)) {
			int one = edge.first;
			if (dist[one] < dist[edge.second]) {
				one = edge.second;
			}

			ll int res = query(b, dep[b] - dep[one] + 1);
			// res = min(res, dp1[b]) << endl;
			// cout << pl(dep[one]) << pl(dep[b]) << endl;
			if (res >= 1e16) {
				cout << "oo" << endl;
			} else {
				cout << res + dist[b] << endl;
			}
		} else {
			cout << "escaped" << endl;
		}
	}
}

int main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
	// cin >> T;
	while (T--)
		solve();
}

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