제출 #1147934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147934		vulestamenkovic	Valley (BOI19_valley)	C++20	100 / 100	226 ms	64168 KiB

valley

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define MAXN (int)1e5+5
#define MAXLG 20
using namespace std;
vector<pii>g[MAXN];
int n, s, q, e, l[MAXN][MAXLG], ss[MAXN], dp[MAXN], dep[MAXN], lg2[MAXN];
array<int,2>l2[MAXN][MAXLG];
pii ed[MAXN];
void precompute() {
	lg2[0] = lg2[1] = 0;
	for (int i = 2; i < MAXN; i++) {
		lg2[i] = lg2[i / 2] + 1;
	}
}
void dfs(int x, int p) {
	if (ss[x]) {
		dp[x] = 0;
	}
	for (pii& y : g[x]) {
		if (y.fi ^ p) {
			dep[y.fi] = dep[x] + 1;
			dfs(y.fi, x);
			dp[x] = min(dp[x], dp[y.fi] + y.se);
		}
	}
}
void dfs2(int x,int p){
	for (int i = 1; i <= lg2[n]; i++) {
		int h = l[x][i - 1];
		l2[x][i]=l2[x][i-1];
		if (h == -1) {
			l[x][i] = -1;
		}
		else {
			l[x][i] = l[h][i - 1];
			l2[x][i][0]+=l2[h][i-1][0];
			if(l2[x][i][1]>l2[h][i-1][1]+l2[x][i-1][0]){
				l2[x][i][1]=l2[h][i-1][1]+l2[x][i-1][0];
			}
		}
	}
	for(pii&y:g[x]){
		if(y.fi^p){
			l[y.fi][0] = x;
			l2[y.fi][0]={y.se,(ss[y.fi]?0ll:min(dp[y.fi],dp[x]+y.se))};
			dfs2(y.fi,x);
		}
	}
}
int lift2(int x,int k){
	int h = x;
	int z=1e18,d=0;
	for (int i = 0; (1 << i) <= k; i++) {
		if ((1 << i) & k) {
			z=min(z,d+l2[h][i][1]);
			d+=l2[h][i][0];
			h = l[h][i];
			if (h == -1) { break; }
		}
	}
	return z;
}
int lift(int x, int k) {
	int h = x;
	for (int i = 0; (1 << i) <= k; i++) {
		if ((1 << i) & k) {
			h = l[h][i];
			if (h == -1) { break; }
		}
	}
	return h;
}
int lca(int a, int b) {
	if (dep[b] > dep[a]) { swap(a, b); }
	a = lift(a, dep[a] - dep[b]);
	if (a == b) { return b; }
	for (int i = lg2[n]; i >= 0; i--) {
		if (l[a][i] != l[b][i]) {
			a = l[a][i];
			b = l[b][i];
		}
	}
	return l[a][0];
}
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); precompute();
	cin >> n >> s >> q >> e;
	fill(dp, dp + n + 1, 1e18);
	for(int i=0;i<=n;i++){
		for(int j=0;j<=lg2[n];j++){
			l2[i][j]={0ll,(int)1e18};
		}
	}
	for (int i = 0; i < n - 1; i++) {
		int a, b, w; cin >> a >> b >> w;
		g[a].emplace_back(b, w);
		g[b].emplace_back(a, w);
		ed[i] = { a,b };
	}
	for (int i = 0; i < s; i++) {
		int x; cin >> x;
		ss[x] = 1;
	}
	l[e][0] = -1;
	dep[e] = 0;
	dfs(e, 0);dfs2(e,0);
	while (q--) {
		int i, r; cin >> i >> r; --i;
		int u = (dep[ed[i].fi] > dep[ed[i].se] ? ed[i].fi : ed[i].se);
		if (lca(r, u) != u) {
			cout << "escaped\n";
			continue;
		}
		int o=min(dp[r],lift2(r,dep[r]-dep[u]));
		if(o==1e18){
			cout<<"oo\n";
		}else{
			cout<<o<<'\n';
		}
	}
}

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