Submission #498567

#	Time	Username	Problem	Language	Result	Execution time	Memory
498567		s_samchenko	Valley (BOI19_valley)	C++17	100 / 100	420 ms	110964 KiB

valley

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC target ("avx2")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define vi vector <int>
using namespace std;
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e15;
const ll mod = 1e9+7;
const int N = 2e5+100;

vector <int> p(N), d(N), ds(N), sz(N, inf);
vector < vector <pii> > g(N);
vector < vector <int> > up(N, vector <int> (20)), jmp = up;
vector <pair <pii, int> > edges(N);
vector <int> c(N);
int n, s, q, r;

void dfs(int v, int pr, int l = 0, int h = 1){
	p[v] = pr;
	d[v] = h;
	ds[v] = l;
	up[v][0] = pr;
	if (c[v]) sz[v] = 0;
	for (int j = 1; j < 20; ++j) up[v][j] = up[up[v][j-1]][j-1];
	
	for (auto i : g[v]){
		int to = i.ff, len = i.ss;
		if (to == pr) continue;
		dfs(to, v, l + len, h+1);
		sz[v] = min(sz[v], sz[to] + len);
	}
}

int lca(int u, int v){
	if (d[u] > d[v]) swap(u, v);
	for (int j = 19, H = d[v] - d[u]; H && j >= 0; --j){
		if (H < (1 << j)) continue;
		H -= (1 << j);
		v = up[v][j];
	}
	if (u == v) return u;
	for (int j = 19; j >= 0; --j){
		int u1 = up[u][j], v1 = up[v][j];
		if (u1 != v1){
			u = u1; v = v1;
		}
	}
	return up[u][0];
}

void solve(){
	cin >> n >> s >> q >> r;
	for (int i = 1; i < n; ++i){
		int a, b, w; cin >> a >> b >> w;
		g[a].pb({b, w});
		g[b].pb({a, w});
		edges[i] = {{a, b}, w};
	}
	for (int i = 0; i < s; ++i){
		int a; cin >> a; c[a] = 1;
	}
	
	dfs(r, r);
	for (int i = 1; i <= n; ++i) jmp[i][0] = sz[i] - ds[i];
	for (int j = 1; j < 20; ++j)
		for (int i = 1; i <= n; ++i) jmp[i][j] = min(jmp[i][j-1], jmp[up[i][j-1]][j-1]);
	
	while (q--){
		int ir, v; cin >> ir >> v;
		int x = edges[ir].ff.ff, y = edges[ir].ff.ss;
		if (!(lca(v, x) == x && lca(v, y) == y)){
			cout << "escaped\n";
			continue;
		}
		if (d[x] > d[y]) swap(x, y);
		if (sz[y] == inf){
			cout << "oo\n";
			continue;
		}
		
		int ans = inf, dd = ds[v];
		for (int j = 19, H = d[v] - d[x]; j >= 0; --j){
			if ((1 << j) > H) continue;
			H -= (1 << j);
			ans = min(ans, jmp[v][j]);
			v = up[v][j];
		}
		ans = min(ans, jmp[y][0]);
		cout << ans + dd << '\n';
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;

	while (tt--){
		solve();
		cout << '\n';
	}
}

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