Submission #1248954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248954		rayan_bd	Valley (BOI19_valley)	C++20	0 / 100	71 ms	22192 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mxN = 1e5 + 100;
const int INF = 1e18;

vector<pair<int, int>> adj[mxN];
int par[mxN], depth[mxN], head[mxN], heavy[mxN], sz[mxN], lt[mxN], val[mxN], dp[mxN], path_sum[mxN], seg[mxN * 4], tin[mxN], tout[mxN], st[mxN], t = -1, t2 = -1;


struct seg_tree1{
	void build(int node, int start, int end){
		if(start == end){
			seg[node] = lt[start];
			return;
		}
		int mid = start + (end - start) / 2;
		build(node * 2 + 1, start, mid);
		build(node * 2 + 2, mid + 1, end);
		seg[node] = min(seg[node * 2 + 1], seg[node * 2 + 2]);
	}

	int query(int node, int start, int end, int l, int r){
		if(start > r || end < l) return INF;
		if(start >= l && end <= r) return seg[node];
		int mid = start + (end - start) / 2;
		return min(query(node * 2 + 1, start, mid, l, r), query(node * 2 + 2, mid + 1, end, l, r));
	}
} tr;

struct hld{
	void dfs(int u = 1, int p = 0){
		depth[u] = depth[p] + 1;
		par[u] = p;
		sz[u] = 1;
		tin[u] = ++t2;
		for(auto it : adj[u]){
			if(it.first ^ p){
				path_sum[it.first] = path_sum[u] + it.second;
				dfs(it.first, u);
				dp[u] = min(dp[u], dp[it.first] + it.second);
				if(sz[heavy[u]] < sz[it.first]){
					heavy[u] = it.first;
				}
			}
		}
		tout[u] = ++t2;
	}

	void dfs_hld(int u = 1, int chain = 1, int p = 0){
		head[u] = chain;
		lt[++t] = dp[u] - path_sum[u];
		st[u] = t;
		if(heavy[u] > 0){
			dfs_hld(heavy[u], chain, u);
		}
		for(auto it : adj[u]){
			if(it.first ^ p && heavy[it.first] ^ it.first){
				dfs_hld(it.first, it.first, u);
			}
		}
	}


	bool subtree(int u, int v){
		return tin[v] >= tin[u] && tout[v] <= tout[u];
	}

	int query(int u, int v) {
	  int ans = INF;
	  while(head[u] != head[v]) {
	    ans = min(ans, tr.query(0, 0, t, st[head[u]], st[u]));
	    u = par[head[u]];
	  }
	  ans = min(ans, tr.query(0, 0, t, st[v], st[u]));
	  return ans;
	}

} hld;


signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr); cout.tie(nullptr);

	int n, s, q, e, u, v, w, edge_id;
	cin >> n >> s >> q >> e;

	vector<pair<int, int>> edge;

	for(int i = 0; i < n - 1; ++i){
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		edge.push_back({u, v});
	}

	for(int i = 1; i <= n; ++i){
		dp[i] = INF;
	}

	for(int i = 0; i < s; ++i){
		cin >> u;
		dp[u] = 0;
	}

	hld.dfs(e, 0);
	hld.dfs_hld(e, e, 0);
	tr.build(0, 0, t);

	while(q--){
		cin >> edge_id >> u; --edge_id;
		int u1 = edge[edge_id].first, u2 = edge[edge_id].second;
		if(hld.subtree(u1, u) && hld.subtree(u2, u) && u != e){
			if(depth[u1] < depth[u2]) swap(u1, u2);
			int curr = hld.query(u, u1) + path_sum[u];
			if(curr >= INF){
				cout << "oo\n";
			}else{
				cout << curr << "\n";
			}
		}else{
			cout << "escaped\n";
		}
	}


	return 0;
}

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