Submission #503728

#	Time	Username	Problem	Language	Result	Execution time	Memory
503728		Arnch	Valley (BOI19_valley)	C++17	100 / 100	446 ms	253248 KiB

valley

// oooo
/*
 be hengam shena mesle y dasto pa cholofti ~
 bepa to masire dahane koose neyofti ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()

const ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969, Log = 22;

int n, s, q, e;
ll par[N][Log], ans[N][Log], ans_h[N][Log], h[N], d[N];

bool mark[N], S[N];

vector<pair<int, int> > G[N], vc;

void get_input() {
	cin >>n >>s >>q >>e;
	for(int i = 1; i <= n - 1; i++) {
		int u, v, w; cin >>u >>v >>w;
		vc.push_back({u, v});
		G[u].push_back({v, w}), G[v].push_back({u, w});
	}
	for(int i = 0; i < s; i++) {
		int u; cin >>u; S[u] = 1;
	}
}

void dfs(int x, int p) {
	mark[x] = 1, par[x][0] = p; 
	if(S[x]) d[x] = 0;
	
	for(int i = 1; i < Log; i++) par[x][i] = par[par[x][i - 1]][i - 1];

	for(auto i : G[x]) if(!mark[i.first]) {
		h[i.first] = h[x] + 1;
		dfs(i.first, x);
		d[x] = min(d[x], d[i.first] + i.second);
	}
}

void main_dfs(int x, int val) {
	mark[x] = 1, ans[x][0] = d[x], ans_h[x][0] = val;
	
	for(int i = 1; i < Log; i++) {
		if(par[x][i] == 0) break;
		
		ans_h[x][i] = ans_h[x][i - 1] + ans_h[par[x][i - 1]][i - 1];
		
		ans[x][i] = min(ans[x][i - 1], ans[par[x][i - 1]][i - 1] + ans_h[x][i - 1]);
	}


	for(auto i : G[x]) if(!mark[i.first]) {
		main_dfs(i.first, i.second);
	}
}

int get_par(int x, int y) {
	for(int i = 0; i < Log; i++) 
		if((y >> i) & 1) 
			x = par[x][i];

	return x;
}

int lca(int x, int y) {
	if(h[x] > h[y]) swap(x, y);
	y = get_par(y, h[y] - h[x]);
	if(x == y) return x;

	for(int i = Log - 1; i >= 0; i--) {
		if(par[x][i] != par[y][i]) {
			x = par[x][i], y = par[y][i];
		}
	}

	return par[x][0];
}

void solve() {
	int e, u; cin >>e >>u;
	e--;

	int l = vc[e].first;
	if(par[l][0] != vc[e].second) l = vc[e].second;
	
	if(lca(l, u) != l) {
		cout<<"escaped" <<'\n';
		return;
	}

	l = par[l][0];
	
	ll cnt = h[u] - h[l], sum = inf, eq = 0;

	for(int i = 0; i < Log; i++) {
		if((cnt >> i) & 1) {
			sum = min(sum, ans[u][i] + eq);

			eq += ans_h[u][i];
		
			u = par[u][i];
		}
	}

	if(sum >= inf) cout<<"oo" <<'\n';
	else cout<<sum <<'\n';
}

int main() {
    fast_io;
	
	get_input();
	
	memset(d, 63, sizeof(d));

	dfs(e, 0);

	memset(mark, 0, sizeof(mark)), memset(ans, 63, sizeof(ans));

	main_dfs(e, 0);	

	while(q--) solve();


    return 0;
}

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