Submission #1249119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249119		rayan_bd	Valley (BOI19_valley)	C++20	0 / 100	79 ms	2884 KiB

valley

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

#define ll long long

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

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

struct seg_tree {
	void build(int node, int start, int end) {
		if (start == end) {
			seg[node] = lt[start];
			return;
		}
		int mid = (start + end) / 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]);
	}

	ll 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) / 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]) {
			int v = it.first, w = it.second;
			if (v != p) {
				path_sum[v] = path_sum[u] + w;
				dfs(v, u);
				dp[u] = min(dp[u], dp[v] + w);
				sz[u] += sz[v];
				if (sz[heavy[u]] < sz[v]) {
					heavy[u] = v;
				}
			}
		}
		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]) {
			dfs_hld(heavy[u], chain, u);
		}
		for (auto it : adj[u]) {
			int v = it.first;
			if (v != p && heavy[u] != v) {
				dfs_hld(v, v, u);
			}
		}
	}

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

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

} hld;

int main() {
	#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr); cout.tie(nullptr);

	int n, s, q, e;
	cin >> n >> s >> q >> e;

	vector<pair<int, int>> edge;

	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});
		edge.emplace_back(u, v);
	}

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

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

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

	while (q--) {
		int edge_id, u;
		cin >> edge_id >> u;
		--edge_id;
		int u1 = edge[edge_id].first;
		int u2 = edge[edge_id].second;

		if (hld.subtree(u1, u) && hld.subtree(u2, u) && u != e) {
			if (depth[u1] < depth[u2]) swap(u1, u2);
			ll answer = hld.query(u, u1);
			if (answer >= INF) {
				cout << "oo\n";
			} else {
				cout << answer << "\n";
			}
		} else {
			cout << "escaped\n";
		}
	}

	return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen("input.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen("output.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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