제출 #337927

#제출 시각아이디문제언어결과실행 시간메모리
337927Kevin_Zhang_TWValley (BOI19_valley)C++17
100 / 100
212 ms37476 KiB
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &val, T nv) {
	return val < nv ? (val = nv, true) : false;
}
template<class T>
bool chmin(T &val, T nv) {
	return nv < val ? (val = nv, true) : false;
}
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int MAX_N = 100010, MAX_K = 17;
const ll inf = 1ll << 60, bound = 1e15;
int n, s, q, e;

vector<pair<int,int>> edge[MAX_N];
bool shop[MAX_N];
int anc[MAX_K][MAX_N], in[MAX_N], out[MAX_N];
ll dp[MAX_K][MAX_N], dep[MAX_N];
inline bool isanc(int a, int b) { return in[a] <= in[b] && out[a] >= out[b]; }
void dfs(int x, int lst) {
	static int t;
	in[x] = t++;
	anc[0][x] = lst;
	dp[0][x] = shop[x] ? dep[x] : inf;
	for (auto [u, w] : edge[x]) if (u != lst) {
		dep[u] = dep[x] + w;
		dfs(u, x);
		chmin(dp[0][x], dp[0][u]);
	}
	out[x] = t;
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> s >> q >> e;
	vector<pair<int,int>> alle(n);
	for (int a, b, w, i = 1;i < n;++i) {
		cin >> a >> b >> w;
		alle[i] = {a, b};
		edge[a].pb(b, w);
		edge[b].pb(a, w);
	}
	for (int p, i = 0;i < s;++i) {
		cin >> p;
		shop[p] = true;
	}
	dfs(e, e);
	for (int i = 1;i <= n;++i) {
		dp[0][i] -= 2 * dep[i];
	}

	int mxlg = 0;

	for (int b = 1;1 << b <= n;++b) {
		mxlg = b;
		for (int i = 1;i <= n;++i) {
			anc[b][i] = anc[b-1][ anc[b-1][i] ];
			dp[b][i] = min(dp[b-1][i], dp[b-1][ anc[b-1][i] ]);
		}
	}

	while (q--) {
		int ID, R;
		cin >> ID >> R;
		auto [a, b] = alle[ID];
		if (dep[a] > dep[b]) swap(a, b);
		// a is up
		// b is down
		if (!isanc(b, R)) cout << "escaped\n";
		else if (shop[R]) cout << 0 << '\n';
		else {
			ll res = dp[0][R] + dep[R];
			int x = R;
			for (int d = mxlg;d >= 0;--d) {
				if (!isanc(anc[d][x], a)) {
					chmin(res, dp[d][x] + dep[R]);
					x = anc[d][x];
				}
			}

			chmin(res, dp[0][x] + dep[R]);
			assert(res >= 0);
			
			if (res > bound)
				cout << "oo\n";
			else cout << res << '\n';
		}
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...