Submission #696544

#	Time	Username	Problem	Language	Result	Execution time	Memory
696544		AmirAli_H1	Valley (BOI19_valley)	C++17	100 / 100	243 ms	59640 KiB

valley

// In the name of Allah

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

typedef long long int	ll;
typedef long double	ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;

#define all(x)		(x).begin(),(x).end()
#define len(x)		((ll) (x).size())
#define F		first
#define S		second
#define pb		push_back
#define sep             ' '
#define endl            '\n'
#define Mp		make_pair
#define debug(x)	cerr << #x << ": " <<  x << endl;
#define kill(x)		cout << x << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define file_io(x,y)	freopen(x, "r", stdin); freopen(y, "w", stdout);

int n, s, q, e;
const int maxn = 1e5 + 5;
const int maxlg = 20;
const ll oo = 1e18;
vector<pll> adj[maxn];
vector<pair<pii, ll>> E;
bool M[maxn];
bool mark[maxn]; int h[maxn]; ll dp[maxn];
int st[maxn], ft[maxn], timer = 0;
int up[maxn][maxlg]; ll W[maxn][maxlg], res[maxn][maxlg];

bool is_gr(int v, int u) {
	return st[v] <= st[u] && ft[v] >= ft[u];
}

void pre_dfs(int v) {
	mark[v] = 1;
	st[v] = timer++;
	if (M[v]) dp[v] = 0;
	else dp[v] = oo;
	for (auto f : adj[v]) {
		auto [u, w] = f;
		if (!mark[u]) {
			h[u] = h[v] + 1;
			pre_dfs(u);
			dp[v] = min(oo, min(dp[v], dp[u] + w));
		}
	}
	ft[v] = timer++;
}

ll get_ans(int u, int k) {
	ll ans = oo, w = 0;
	for (int i = 0; i < maxlg; i++) {
		if (k & (1 << i)) {
			ans = min(ans, w + res[u][i]);
			w += W[u][i]; u = up[u][i];
		}
	}
	return ans;
}

void dfs_res(int v, int p = -1, ll wx = 0) {
	mark[v] = 1;
	
	up[v][0] = (p != -1) ? p : v;
	W[v][0] = wx; res[v][0] = dp[v];
	for (int i = 1; i < maxlg; i++) {
		int u = up[v][i - 1];
		up[v][i] = up[u][i - 1];
		W[v][i] = W[v][i - 1] + W[u][i - 1];
		res[v][i] = min(oo, min(res[v][i - 1], W[v][i - 1] + res[u][i - 1]));
	}
	
	for (auto f : adj[v]) {
		auto [u, w] = f;
		if (!mark[u]) {
			dfs_res(u, v, w);
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> s >> q >> e; e--;
	for (int i = 0; i < n - 1; i++) {
		int u, v; ll w;
		cin >> u >> v >> w; u--; v--;
		adj[u].pb(Mp(v, w)); adj[v].pb(Mp(u, w));
		E.pb(Mp(Mp(u, v), w));
	}
	
	for (int i = 0; i < s; i++) {
		int u;
		cin >> u; u--;
		M[u] = 1;
	}
	
	fill(mark, mark + n, 0); pre_dfs(e);
	fill(mark, mark + n, 0); dfs_res(e);
	
	while (q--) {
		int i, u;
		cin >> i >> u; i--; u--;
		auto [u1, v1] = E[i].F;
		if (h[u1] < h[v1]) swap(u1, v1);
		if (is_gr(u1, u)) {
			int k = h[u] - h[u1] + 1;
			ll ans = get_ans(u, k);
			if (ans < oo) cout << ans << endl;
			else cout << "oo" << endl;
		}
		else {
			cout << "escaped" << endl;
		}
	}
	
	return 0;
}

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