Submission #730734

#	Time	Username	Problem	Language	Result	Execution time	Memory
730734		gagik_2007	Valley (BOI19_valley)	C++17	100 / 100	282 ms	60364 KiB

valley

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
#include <bitset>
using namespace std;

typedef long long ll;
typedef long double ld;

#pragma GCC optimize("Ofast")

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 100007;
const ll LG = 21;
ll n, m, k;
vector<pair<int, ll>>g[N];
int up[N][LG];
ll dist[N][LG]; // the distance between v and up[v][i]
ll dp[N][LG]; // the distance to the closest marked node to v in the subtree of up[v][i]
int tin[N], tout[N];
ll st[N]; // dp for v's subtree
int timer = 0;
bool marked[N];
int lft[N], rgh[N];

void dfs(int v, int par, ll w) {
	tin[v] = timer++;
	up[v][0] = par;
	dist[v][0] = w;
	st[v] = INF;
	if (marked[v]) {
		st[v] = 0;
	}
	for (auto e : g[v]) {
		int to = e.ff;
		ll d = e.ss;
		if (to != par) {
			dfs(to, v, d);
			st[v] = min(st[v], st[to] + d);
		}
	}
	tout[v] = timer++;
}

void precalc(int root) {
	dfs(root, root, 0);
	for (int v = 1; v <= n; v++) {
		dp[v][0] = min(st[up[v][0]] + dist[v][0], st[v]);
	}
	for (int i = 1; i < LG; i++) {
		for (int v = 1; v <= n; v++) {
			up[v][i] = up[up[v][i - 1]][i - 1];
			dist[v][i] = dist[v][i - 1] + dist[up[v][i - 1]][i - 1];
			dp[v][i] = min(dp[v][i - 1], dp[up[v][i - 1]][i - 1] + dist[v][i - 1]);
		}
	}
}

bool is_papa(int v, int u) {
	return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}

ll get_ans(int v, int u) {
	if (v == u) {
		return st[v];
	}
	ll cur_dist = 0;
	ll cur_ans = INF;
	for (int i = LG - 1; i >= 0; i--) {
		if (!is_papa(up[v][i], u)) {
			cur_ans = min(cur_ans, cur_dist + dp[v][i]);
			cur_dist += dist[v][i];
			v = up[v][i];
		}
	}
	cur_ans = min(cur_ans, cur_dist + dp[v][0]);
	return cur_ans;
}

int get_lower(int e) {
	if (is_papa(lft[e], rgh[e]))return rgh[e];
	return lft[e];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int root;
	cin >> n >> k >> m >> root;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		ll w;
		cin >> w;
		g[x].push_back({ y,w });
		g[y].push_back({ x,w });
		lft[i] = x;
		rgh[i] = y;
	}
	for (int i = 0; i < k; i++) {
		int v;
		cin >> v;
		marked[v] = true;
	}
	precalc(root);
	for (int i = 0; i < m; i++) {
		int e, v;
		cin >> e >> v;
		int u = get_lower(e);
		if (!is_papa(u, v)) {
			cout << "escaped\n";
		}
		else {
			ll vl = get_ans(v, u);
			if (vl >= INF) {
				cout << "oo" << endl;
			}
			else {
				cout << vl << endl;
			}
		}
	}
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

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