제출 #1328648

#제출 시각아이디문제언어결과실행 시간메모리
1328648tkm_algorithmsValley (BOI19_valley)C++20
100 / 100
124 ms49784 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;
const int NMAX = 1e5+10;
const int inf = 1e5*1e9+10;
struct edge{
	int v, w, id;
};

P E[NMAX];
vector<edge> g[NMAX];
int tin[NMAX], tout[NMAX], dep[NMAX];
int d[NMAX], s[NMAX], opt[NMAX];
int d2[NMAX], par[NMAX][17], mn[NMAX][17];
int t = 0;

void dfs(int nd, int p = -1, int v = -1) {
	tin[nd] = t++, opt[nd] = v;
	for (auto ch: g[nd]) {
		if (ch.v == p)continue;
		E[ch.id] = {nd, ch.v};
		s[ch.v] = s[nd]+ch.w;
		dep[ch.v] = dep[nd]+1;
		dfs(ch.v, nd, (d[nd] == 0?nd:v));
		d[nd] = min(d[nd], d[ch.v]+ch.w);
	}
	
	d2[nd] = d[nd]-s[nd];
	tout[nd] = t-1;
}

void dfs2(int nd, int p = -1) {
	par[nd][0] = p; mn[nd][0] = (p == -1?inf:d2[p]);
	
	rep(i, 1, 17) {
		if (par[nd][i-1] == -1)break;
		par[nd][i] = par[par[nd][i-1]][i-1];
		mn[nd][i] = min(mn[nd][i-1], mn[par[nd][i-1]][i-1]);
	}
	
	for (auto ch: g[nd]) {
		if (ch.v == p)continue;
		dfs2(ch.v, nd);
	}
}

bool f(int l, int r, int x) {
	if (l <= x && x <= r)return 1;
	return 0;
}

void solve() {
	memset(par, -1, sizeof par);
	int n, ss, q, e;
	cin >> n >> ss >> q >> e;
	
	rep(i, 1, n+1) {
		d[i] = d2[i] = inf;
		//rep(j)
	}
	rep(i, 1, n) {
		int u, v, w; cin >> u >> v >> w;
		g[u].push_back({v, w, i});
		g[v].push_back({u, w, i});
	}
	
	rep(i, 0, ss) {
		int c; cin >> c;
		d[c] = 0;
	}
	
	dfs(e);
	dfs2(e);
	
	//cout << d2[7] << nl;
	while (q--) {
		int I, R; cin >> I >> R;
		int v = E[I].second;
		int a = f(tin[v], tout[v], tin[R]);
		if (!a)cout << "escaped\n";
		else {
			int uc = inf, dt = inf, len = dep[R]-dep[v], ro = R;
			if (opt[R] != -1 && f(tin[v], tout[v], tin[opt[R]]))uc = s[R]-s[opt[R]];
			int res = min(d[R], min(d[v]+s[R]-s[v], uc));
			while (len) {
				for (int i = 16; i >= 0; --i)
					if (par[R][i] != -1 && dep[par[R][i]] >= dep[v]) {
						dt = min(dt, mn[R][i]); len -= (1<<i);
						R = par[R][i];
					}
			}
			res = min(res, dt+s[ro]);
			//cout << s[R] << " " << dt << nl;
			if (res == inf)cout << "oo" << nl;
			else cout << res << nl;
		}
	}	
	
	//cout << s[2] << nl;
	//cout << d2[5] << " " << mn[2][0] << nl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...