Submission #1213788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213788		g4yuhg	Valley (BOI19_valley)	C++20	100 / 100	128 ms	51872 KiB

valley

//Huyduocdithitp
#include <bits/stdc++.h>
#define int long long
typedef long long ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 100005
using namespace std;
struct Edge {
	ll u, v, w;
} canh[N]; // u la con cua v
ll n, s, q, e, high[N], dep[N], par[N][LOG + 2], spe[N], spe1[N][LOG + 2];
ll in[N], out[N], timeDfs;
vector<pii> adj[N];
void dfs(ll u, ll parent) {
	in[u] = ++ timeDfs;
	for (auto v : adj[u]) {
		if (v.fi == parent) continue;
		par[v.fi][0] = u;
		high[v.fi] = high[u] + 1;
		dep[v.fi] = dep[u] + v.se;
		dfs(v.fi, u);
	}
	out[u] = timeDfs;
}
bool is_an(ll u, ll v) { // u co phai to tien cua v khong
	return in[u] <= in[v] && in[v] <= out[u];
}
void prepare() {
	for (int j = 1; j <= LOG; j ++) {
		for (int i = 1; i <= n; i ++) {
			ll p = par[i][j - 1];
			par[i][j] = par[p][j - 1];
			spe1[i][j] = min(spe1[i][j - 1], spe1[p][j - 1]);
		}
	}
}
ll kth_par(ll u, ll k) {
	for (int j = LOG; j >= 0; j --) {
		if (k >= (1 << j)) {
			k -= (1 << j);
			u = par[u][j];
		}
	}
	return u;
}
ll get1(ll u, ll k) {
	k ++ ;
	ll res = inf;
	for (int j = LOG; j >= 0; j --) {
		if (k >= (1 << j)) {
			k -= (1 << j);
			//cout << u << " " << k << " " << j << endl;
			res = min(res, spe1[u][j]);
			u = par[u][j];
		}
	}
	return res;
}
ll lca(ll u, ll v) {
	if (high[u] > high[v]) swap(u, v);
	for (int j = LOG; j >= 0; j --) {
		if ((1 << j) <= high[v] - high[u]) {
			v = par[v][j];
		}
	}
	if (u == v) return u;
	for (int j = LOG; j >= 0; j --) {
		if (par[v][j] != par[u][j]) {
			u = par[u][j];
			v = par[v][j];
		}
	}
	return par[u][0];
}
void dfs1(ll u, ll parent) {
	if (spe[u] == -1) spe[u] = inf;
	else spe[u] = dep[u];
	for (auto v : adj[u]) {
		if (v.fi == parent) continue;
		dfs1(v.fi, u);
		spe[u] = min(spe[u], spe[v.fi]);
	}
	spe1[u][0] = spe[u] - 2 * dep[u];
}
ll solve2(ll u, ll R) {
	ll res = inf;
	res = min(res, spe[R] - dep[R]);
	res = min(res, get1(R, high[R] - high[u]) + dep[R]);
	return res;
}
void solve(ll I, ll R) {
	ll u = canh[I].u;
	//cout << I << " " << u << " " << R << " " << is_an(u, R) << endl;
	if (is_an(u, R) == 0) {
		cout << "escaped" << endl;
		return;
	}
	//cout << "chua thoat" << endl;
	ll res = solve2(u, R);
	if (res > 1e14) {
		cout << "oo" << endl;
	}
	else {
		cout << res << endl;
	}
}
signed main(void) {
    faster;
    cin >> n >> s >> q >> e;
    for (int i = 1; i <= n - 1; i ++) {
    	ll u, v, w;
    	cin >> u >> v >> w;
    	adj[u].push_back({v, w});
    	adj[v].push_back({u, w});
    	canh[i] = {u, v, w};
    	spe[i] = -1; spe[i + 1] = -1;
    }
    dfs(e, e);
    for (int i = 1; i <= s; i ++) {
    	ll u; cin >> u; spe[u] = dep[u];
    }
    dfs1(e, e);
    for (int i = 1; i <= n - 1; i ++) {
    	if (canh[i].u == par[canh[i].v][0]) {
    		swap(canh[i].u, canh[i].v); // u luon la con cua v
    	}
    }
    //cout << "debug: " << is_an(3, 2) << endl;
    prepare();
    for (int i = 1; i <= q; i ++) {
    	ll I, R;
    	cin >> I >> R;
    	solve(I, R);
    }
    return 0;
}

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