Submission #493841

#	Time	Username	Problem	Language	Result	Execution time	Memory
493841		yungyao	Valley (BOI19_valley)	C++17	100 / 100	159 ms	36732 KiB

valley

using namespace std;
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
#include <set>
#include <stack>
#include <queue>

typedef long long LL;
typedef pair<int,int> pii;
#define pb push_back
#define mkp make_pair
#define F first
#define S second
#define iter(x) x.begin(),x.end()
#define REP(n) for (int __=n;__--;)
#define REP0(i,n) for (int i=0;i<n;++i)
#define REP1(i,n) for (int i=1;i<=n;++i)

const int maxn = 1e5+10, mod = 0;
const LL inf = 1e18;

int anc[17][maxn];
LL mx[17][maxn], prefix[maxn];
vector <pii> adj[maxn];
struct EDGE{
	int u,v,w;

	void input(){
		cin >> u >> v >> w;
		adj[u].pb(mkp(v,w));
		adj[v].pb(mkp(u,w));
	}
}edge[maxn];

int dep[maxn], frv[maxn];
bool have_shop[maxn];
void dfs(int x,int fr){
	if (fr){
		dep[x] = dep[fr] + 1;
		anc[0][x] = fr;
		prefix[x] = prefix[fr] + frv[x];
	}
	if (have_shop[x]) mx[0][x] = 0;
	else mx[0][x] = inf;
	for (auto &[i,w]:adj[x]) if (i != fr){
		frv[i] = w;
		dfs(i, x);
		mx[0][x] = min(mx[0][x], mx[0][i] + w);
	}
}

int jump(int x, int k){
	if (k) for (int i=0,b=__lg(k);i<=b;++i) if ((k >> i) & 1) x = anc[i][x];
	return x;
}
LL premx(int x, int k){
	LL ret = mx[0][x];
	x = anc[0][x];
	if (k) for (int i=0,b=__lg(k);i<=b;++i) if ((k >> i) & 1){
		ret = max(ret, mx[i][x]);
		x = anc[i][x];
	}
	return ret;
}

void solve(){
	int n, s, q, e;

	cin >> n >> s >> q >> e;
	REP1(i,n-1){
		edge[i].input();
	}
	REP(s){
		int x;

		cin >> x;
		have_shop[x] = true;
	}
	dfs(e, 0);
	REP1(i, n-1) if (dep[edge[i].v] > dep[edge[i].u]) swap(edge[i].u, edge[i].v);
	REP1(i, n) mx[0][i] = prefix[i] - mx[0][i];
	REP1(i, 16) REP1(j, n) anc[i][j] = anc[i-1][anc[i-1][j]], mx[i][j] = max(mx[i-1][j], mx[i-1][anc[i-1][j]]);

	REP0(i, q){
		int c, r;

		cin >> c >> r;
		c = edge[c].u;
		if (dep[r] < dep[c] or jump(r, dep[r] - dep[c]) != c) cout << "escaped\n";
		else{
			LL ans = prefix[r] - premx(r, dep[r] - dep[c]);
			//cout << prefix[r] << ' ' << premx(r, dep[r] - dep[c]) << ' ';

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

	/*REP0(i, q){
		if (o[i] == -1) cout << "escaped\n";
		else if (o[i] != inf) cout << o[i] << '\n';
		else cout << "oo\n";
	}*/
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	solve();

	return 0;
}

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