Submission #1082420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082420		vuavisao	Valley (BOI19_valley)	C++14	100 / 100	81 ms	41148 KiB

valley

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

const int N = (int) 1e5 + 10;
const long long INF = (long long) 1e18;

int n, numStores, q, escape;
tuple<int, int, int> edges[N];
int positionStore[N];

namespace sub12 {
	bool check() {
		return (1ll * n * q <= (long long) 1e7);
	}
	
	vector<vector<pair<int, int>>> g;
	long long dist[N];

	void solve() {
		g.resize(n + 1);
		while (q -- > 0) {
			for (int u = 1; u <= n; ++ u) {
				g[u].clear();
				dist[u] = INF;
			}
			int path, curPosition; cin >> path >> curPosition;
			for (int i = 1; i <= n - 1; ++ i) {
				if (i == path) continue;
				int u = get<0>(edges[i]), v = get<1>(edges[i]), w = get<2>(edges[i]);
				g[u].push_back(make_pair(v, w));
				g[v].push_back(make_pair(u, w));
			}
			queue<int> q;
			q.push(curPosition);
			dist[curPosition] = 0;
			while (!q.empty()) {
				int u = q.front(); q.pop();
				for (const auto& x : g[u]) {
					int v = x.first, w = x.second;
					if (dist[v] < INF) continue;
					dist[v] = dist[u] + w;
					q.push(v);
				}
			}
			if (dist[escape] < INF) {
				cout << "escaped";
			}
			else {
				long long res = INF;
				for (int i = 1; i <= numStores; ++ i) {
					res = min(res, dist[positionStore[i]]);
				}
				if (res >= INF) {
					cout << "oo";
				}
				else {
					cout << res;
				}
			}
			cout << '\n';
		}
	}
}

namespace sub3 {
	bool check() {
		return (numStores == n);
	}

	vector<vector<int>> g;

	int Lg, dist[N], parent[20][N];
	int cnt, in[N], out[N];

	void dfs(int u, int p) {
		in[u] = ++ cnt;
		for (const auto& v : g[u]) {
			if (v == p) continue;
			parent[0][v] = u;
			dist[v] = dist[u] + 1;
			dfs(v, u);
		}
		out[u] = cnt;
	};

	int lca(int u, int v) {
		if (dist[u] < dist[v]) swap(u, v);

		int delta = dist[u] - dist[v];
		for (int lg = Lg; lg >= 0; -- lg) {
			if (((delta >> lg) & 1)) {
				u = parent[lg][u];
			}
		}
		if (u == v) return u;
		
		for (int lg = Lg; lg >= 0; -- lg) {
			if (parent[lg][u] != parent[lg][v]) {
				u = parent[lg][u];
				v = parent[lg][v];
			}
		}
		return parent[0][u];
	}

	bool isChild(int u, int p) {
		return in[p] <= in[u] && out[u] <= out[p];
	}

	void solve() {
		g.resize(n + 1);
		for (int i = 1; i <= n - 1; ++ i) {
			int u = get<0>(edges[i]), v = get<1>(edges[i]);
			g[u].push_back(v);
			g[v].push_back(u);
		}

		Lg = __lg(n);
		dist[1] = 1; dfs(1, 0);
		for (int lg = 1; lg <= Lg; ++ lg) {
			for (int u = 1; u <= n; ++ u) {
				parent[lg][u] = parent[lg - 1][parent[lg - 1][u]];
			}
		}

		for (int i = 1; i <= n - 1; ++ i) {
			int u = get<0>(edges[i]), v = get<1>(edges[i]);
			if (in[u] > in[v]) swap(u, v);
			edges[i] = make_tuple(u, v, get<2>(edges[i]));
		}

		while (q -- > 0) {
			int path, curPosition; cin >> path >> curPosition;
			int anc = lca(curPosition, escape);
			
			int u = get<0>(edges[path]);
			int v = get<1>(edges[path]);
			if (isChild(u, anc) && ((isChild(curPosition, u) && isChild(curPosition, v)) || (isChild(escape, u) && isChild(escape, v)))) {
				cout << 0;
			}
			else {
				cout << "escaped";
			}
			cout << '\n';
		}
	}
}

namespace sub4 {
	vector<vector<pair<int, int>>> g;
	long long sDist[N];

	int Lg, dist[N], parent[20][N];
	int cnt, in[N], out[N];
	long long near[N], minStore[20][N];

	void dfs(int u, int p) {
		in[u] = ++ cnt;
		for (const auto& x : g[u]) {
			int v = x.first, w = x.second;
			if (v == p) continue;
			parent[0][v] = u;
			dist[v] = dist[u] + 1;
			sDist[v] = sDist[u] + w;
			dfs(v, u);
		}
		out[u] = cnt;
	};

	void dfsNear(int u, int p) {
		for (const auto& x : g[u]) {
			int v = x.first;
			if (v == p) continue;
			dfsNear(v, u);
			near[u] = min(near[u], near[v]);
		}
	}

	int lca(int u, int v) {
		if (dist[u] < dist[v]) swap(u, v);

		int delta = dist[u] - dist[v];
		for (int lg = Lg; lg >= 0; -- lg) {
			if (((delta >> lg) & 1)) {
				u = parent[lg][u];
			}
		}
		if (u == v) return u;
		
		for (int lg = Lg; lg >= 0; -- lg) {
			if (parent[lg][u] != parent[lg][v]) {
				u = parent[lg][u];
				v = parent[lg][v];
			}
		}
		return parent[0][u];
	}

	long long minPath(int u, int p) {
		long long res = INF;
		int delta = dist[u] - dist[p];
		for (int lg = Lg; lg >= 0; -- lg) {
			if (((delta >> lg) & 1)) {
				res = min(res, minStore[lg][u]);
				u = parent[lg][u];
			}
		}
		res = min(res, near[p]);
		return res;
	}

	bool isChild(int u, int p) {
		return in[p] <= in[u] && out[u] <= out[p];
	}

	void solve() {
		g.resize(n + 1);
		for (int i = 1; i <= n - 1; ++ i) {
			int u = get<0>(edges[i]), v = get<1>(edges[i]), w = get<2>(edges[i]);
			g[u].push_back(make_pair(v, w));
			g[v].push_back(make_pair(u, w));
		}

		for (int u = 1; u <= n; ++ u) near[u] = INF;

		Lg = __lg(n);
		dist[escape] = 1; dfs(escape, 0);

		for (int i = 1; i <= numStores; ++ i) near[positionStore[i]] = sDist[positionStore[i]];
		dfsNear(escape, 0);
		for (int u = 1; u <= n; ++ u) {
			if (near[u] < INF) {
				near[u] -= 2ll * sDist[u];
			}
			minStore[0][u] = near[u];
		}
		

		for (int lg = 1; lg <= Lg; ++ lg) {
			for (int u = 1; u <= n; ++ u) {
				parent[lg][u] = parent[lg - 1][parent[lg - 1][u]];
				minStore[lg][u] = min(minStore[lg - 1][u], minStore[lg - 1][parent[lg - 1][u]]);
			}
		}

		for (int i = 1; i <= n - 1; ++ i) {
			int u = get<0>(edges[i]), v = get<1>(edges[i]);
			if (in[u] > in[v]) swap(u, v);
			edges[i] = make_tuple(u, v, get<2>(edges[i]));
		}

		while (q -- > 0) {
			int path, curPosition; cin >> path >> curPosition;
			int rem = get<1>(edges[path]);
			if (!isChild(curPosition, rem)) {
				cout << "escaped";
			}
			else {
				long long res = minPath(curPosition, rem) + sDist[curPosition];
				if (res >= INF) {
					cout << "oo";
				}
				else {
					cout << res;
				}
			}
			cout << '\n';
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> numStores >> q >> escape;
	for (int i = 1; i <= n - 1; ++ i) {
		int u, v, w; cin >> u >> v >> w;
		edges[i] = make_tuple(u, v, w);
	}
	for (int i = 1; i <= numStores; ++ i) cin >> positionStore[i];
	if (sub12::check()) {
		sub12::solve();
		return 0;
	}
	if (sub3::check()) {
		sub3::solve();
		return 0;
	}
	sub4::solve();
	return 0;
}

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