Submission #729274

#	Time	Username	Problem	Language	Result	Execution time	Memory
729274		WonderfulWhale	Valley (BOI19_valley)	C++17	100 / 100	240 ms	53784 KiB

valley

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

#define int int64_t
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

int n, s, q, e;

vector<pii> G[100009];
bool shop[100009];
int shop_dis[100009];
int dep[100009];
int val[100009];
int tin[100009], tout[100009], T;
pii jp2[100009][20];

int dis(int x, int y) {
	return abs(dep[x]-dep[y]);
}

void dfs(int x, int y) {
	tin[x] = ++T;
	shop_dis[x] = 1e18;
	if(shop[x]) shop_dis[x] = 0;
	for(auto [z, d]:G[x]) {
		if(z==y) continue;
		dep[z] = dep[x] + d;
		dfs(z, x);
		shop_dis[x] = min(shop_dis[x], shop_dis[z]+d);
	}
	val[x] = shop_dis[x]-dis(x, e);
	tout[x] = ++T;
}

void dfs2(int x, int y) {
	jp2[x][0] = {y, val[y]};
	for(int i=1;i<20;i++) {
		jp2[x][i].st = jp2[jp2[x][i-1].st][i-1].st;
		jp2[x][i].nd = min(jp2[x][i-1].nd, jp2[jp2[x][i-1].st][i-1].nd);
	}
	for(auto [z, d]:G[x]) {
		if(z!=y) dfs2(z, x);
	}
}

bool is_ancestor(int x, int y) {
	return tin[x]<=tin[y]&&tout[x]>=tout[y];
}

int solve(int a, int b) {
	if(a==b) return val[a];
	int ans = val[a];
	for(int i=19;i>=0;i--) {
		if(!is_ancestor(jp2[a][i].st, b)) {
			ans = min(ans, jp2[a][i].nd);
			a = jp2[a][i].st;
		}
	}
	ans = min(ans, jp2[a][0].nd);
	return ans;
}

vector<pii> edges;

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> s >> q >> e;
	for(int i=0;i<n-1;i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edges.pb({a, b});
		G[a].pb({b, c});
		G[b].pb({a, c});
	}
	for(int i=0;i<s;i++) {
		int x;
		cin >> x;
		shop[x] = true;
	}
	dfs(e, 0);
	tout[0] = ++T;
	val[e] = 1e18;
	dfs2(e, 0);
	for(int i=0;i<q;i++) {
		int x, a;
		cin >> x >> a;
		x--;
		int b = edges[x].nd;
		if(dep[edges[x].st]>dep[edges[x].nd]) b = edges[x].st;
		if(a!=b&&!is_ancestor(b, a)) {
			cout << "escaped\n";
			continue;
		}
		int ans = solve(a, b);
		if(ans>1e17) {
			cout << "oo\n";
		} else {
			cout << ans+dis(a, e) << "\n";
		}
	}
}

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