Submission #491848

#	Time	Username	Problem	Language	Result	Execution time	Memory
491848		codr0	Valley (BOI19_valley)	C++14	36 / 100	3088 ms	18572 KiB

valley

//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
template<class A> string to_string(complex<A> c) { 
	stringstream ss; ss << c; return ss.str(); }
string to_string(vector<bool> v) { 
	string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
	string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
	return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
	bool fst = 1; string res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += to_string(x);
	}
	res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
	return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 1e5 + 10, LOG = 20;
const ll INF = 1e18;
int n, s, q, e, T, st[MAXN], ft[MAXN], par[LOG][MAXN], h[MAXN];
vector<pair<int, int>> adj[MAXN];
pair<int, int> edge[MAXN], shop[MAXN];
ll d[MAXN];

void dfs (int v, int p) {
	st[v] = T++;
	par[0][v] = p;
	for (auto tmp : adj[v]) {
		int i = tmp.first;
		if (i == p) {
			continue;
		}
		d[i] = d[v] + tmp.second;
		h[i] = h[v] + 1;
		dfs(i, v);
	}
	ft[v] = T - 1;
}

inline int lca (int v, int u) {
	if (h[v] > h[u]) {
		swap(v, u);
	}
	while (h[v] != h[u]) {
		u = par[__builtin_ctz(h[u] - h[v])][u];
	}
	if (v == u) {
		return v;
	}
	for (int bit = LOG - 1; ~bit; bit--) {
		if (par[bit][v] != par[bit][u]) {
			v = par[bit][v], u = par[bit][u];
		}
	}
	return par[0][v];
}


inline ll dis (int v, int u) {
	return d[v] + d[u] - 2 * d[lca(u, v)];
}

int main() {
	ios::sync_with_stdio(0);
#ifndef LOCAL
	cin.tie(0);
#endif
	cin >> n >> s >> q >> e;
	e--;
	for (int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
		edge[i] = {u, v};
	}
	dfs(e, e);
	for (int bit = 1; bit < LOG; bit++) {
		for (int i = 0; i < n; i++) {
			par[bit][i] = par[bit - 1][par[bit - 1][i]];
		}
	}
	for (int i = 0; i < s; i++) {
		cin >> shop[i].second;
		shop[i].second--;
		shop[i].first = st[shop[i].second];
	}
	sort(shop, shop + s);

	auto low = [&](pair<int, int> p) {
		return st[p.first] > st[p.second] ? p.first : p.second;
	};
	auto is_ans = [&](int v, int u) {
		return st[u] >= st[v] && ft[u] <= ft[v];
	};

	while (q--) {
		int i, r;
		cin >> i >> r;
		i--, r--;
		int v = low(edge[i]);
		if (is_ans(v, r)) {
			int l = lower_bound(shop, shop + s, make_pair(st[v], -1)) - shop, tmp = upper_bound(shop, shop + s, make_pair(ft[v], (int)1e9)) - shop - 1;
			ll ans = INF;
			for (int j = l; j <= tmp; j++) {
				ans = min(ans, dis(r, shop[j].second));
			}
			if (ans == INF) {
				cout << "oo" << '\n';
			}
			else {
				cout << ans << '\n';
			}
		}
		else {
			cout << "escaped" << '\n';
		}
	}
}

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