Submission #1082387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082387		vuavisao	Valley (BOI19_valley)	C++14	36 / 100	71 ms	19924 KiB

valley

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

using ll = long long;

const int N = 100'000 + 10;
const ll INF = 1'000'000'000'000'000'000;

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

namespace sub12 {
	bool check() {
		return (1ll * n * q <= 10'000'000);
	}
	
	vector<vector<pair<int, int>>> g;
	ll 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 {
				ll 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 rem = get<0>(edges[path]);
			if (isChild(rem, anc) && (isChild(curPosition, rem) || isChild(escape, rem))) {
				cout << 0;
			}
			else {
				cout << "escaped";
			}
			cout << '\n';
		}
	}
}

int32_t main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::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;
	}
	return (0 ^ 0);
}

/// Code by vuavisao

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