Submission #477503

#	Time	Username	Problem	Language	Result	Execution time	Memory
477503		Sohsoh84	Valley (BOI19_valley)	C++17	100 / 100	334 ms	83512 KiB

valley

// ¯\_(ツ)_/¯
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;
 
const ll MAXN = 1e6 + 10;
const ll INF = 1e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;
const ll LOG = 20; 
 
int n, s, q, e, H[MAXN], tin[MAXN], tout[MAXN], T, par[MAXN][LOG];
vector<pair<int, int>> adj[MAXN];
vector<pair<int, int>> edges;
bool B[MAXN], sub_g[MAXN];
ll dist[MAXN], dp_up[MAXN], Down[MAXN][LOG], Up[MAXN][LOG];
pair<pll, pll> dp[MAXN]; 
 
void dfs(int v, int p) {
	par[v][0] = p;
	tin[v] = T++;
	H[v] = H[p] + 1;
	dp[v] = {{INF, 0}, {INF, 0}};
 
	if (v == e) sub_g[v] = true;
	if (B[v]) dp[v].X = {0, v};
	
	for (auto e : adj[v]) {
		int u = e.X, w = e.Y;
		if (u == p) continue;
 
		dist[u] = dist[v] + w;
		dfs(u, v);
		sub_g[v] |= sub_g[u];	
 
		if (dp[u].X.X + w < dp[v].X.X) {
			dp[v].Y = dp[v].X;
			dp[v].X = {dp[u].X.X + w, u};
		} else if (dp[u].X.X + w < dp[v].Y.X) dp[v].Y = {dp[u].X.X + w, u};
	}
 
	tout[v] = T++;
}
 
bool SubG(int v, int u) {
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}
 
void dfs_up(int v, int p, int w) {
	dp_up[v] = min(INF, dp_up[p] + w);
	if (dp[p].X.Y != v) dp_up[v] = min(dp[p].X.X + w, dp_up[v]);
	if (dp[p].Y.Y != v) dp_up[v] = min(dp[p].Y.X + w, dp_up[v]);
	if (B[v]) dp_up[v] = 0;
 
	for (auto e : adj[v]) 
		if (e.X != p)
			dfs_up(e.X, v, e.Y);
}
 
ll Val(int v, int u) {
	if (dp[v].X.Y != u) return dp[v].X.X;
	else return dp[v].Y.X;
}
 
int Par(int v, int k) {
	for (int i = LOG - 1; i >= 0; i--) 
		if (k & (1 << i))
			v = par[v][i];
	return v;
}
 
int LCA(int v, int u) {
	if (H[v] < H[u]) swap(v, u);
	v = Par(v, H[v] - H[u]);
	if (v == u) return v;
 
	for (int i = LOG - 1; i >= 0; i--)
		if (par[v][i] != par[u][i])
			v = par[v][i], u = par[u][i];
	return par[v][0];
}
 
ll LD(int v, int k) {
	int R = v;
	if (k < 0) return INF;
	ll ans = dp[v].X.X;
 
	for (int i = LOG - 1; i >= 0; i--) {
		if (k & (1 << i)) {
			ans = min(ans, Down[v][i] + dist[R] - dist[v]);
			v = par[v][i];
		}
	}
 
	return ans;
}
 
ll UD(int v, int k) {
	if (k <= 0) return INF;	
	ll ans = INF;
 
	int R = Par(v, k);
	for (int i = LOG - 1; i >= 0; i--) {
		if (k & (1 << i)) {
			ans = min(ans, Up[v][i] + dist[par[v][i]] - dist[R]);
			v = par[v][i];
		}
	}
 
	return ans;
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> s >> q >> e;
	for (int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		edges.push_back({u, v});
	}
 
	for (int i = 0; i < s; i++) {
		int x;
		cin >> x;
		B[x] = true;
	}
	
	dp_up[0] = INF;
	dp[0] = {{INF, INF}, {INF, INF}};
 
	dfs(1, 0);
	dfs_up(1, 0, 0);
	
	for (int i = 0; i <= n; i++) Down[i][0] = min(dp[i].X.X, dp[par[i][0]].X.X + dist[i] - dist[par[i][0]]), Up[i][0] = Val(par[i][0], i);
 
	for (int i = 1; i < LOG; i++) {
		for (int v = 1; v <= n; v++) {
			int p = par[v][i - 1];
			par[v][i] = par[p][i - 1];
			Down[v][i] = min(Down[v][i - 1], Down[p][i - 1] + dist[v] - dist[p]);
			Up[v][i] = min(Up[p][i - 1], Up[v][i - 1] + dist[p] - dist[par[v][i]]);
		}
	}
	
	while (q--) {
		int r, v;
		cin >> r >> v;
		int e_v = edges[r - 1].X, e_u = edges[r - 1].Y;
		if (H[e_v] < H[e_u]) swap(e_v, e_u);
 
		if (SubG(e_v, v)) {
			if (sub_g[e_v]) {
				cout << "escaped" << endl;
				continue;
			}
			
			ll ans = min(INF, LD(v, H[v] - H[e_v]));
			if (ans >= INF) cout << "oo" << endl;
			else cout << ans << endl;
			continue;
		}
 
		if (!sub_g[e_v]) {
			cout << "escaped" << endl;
			continue;
		}
 
		int lca = LCA(e_u, v);
		ll ans = dp_up[lca] + dist[v] - dist[lca];
		ans = min(ans, UD(e_v, H[e_v] - H[lca]) + dist[v] - dist[lca]);
		ans = min(ans, LD(v, H[v] - H[lca] - 1));
 
		if (ans >= INF) cout << "oo" << endl;
		else cout << ans << endl;
	}
	return 0;
}

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