oj.uz

Submission #491848

# Submission time Handle Problem Language Result Execution time Memory
491848 2021-12-04T18:26:25 Z codr0 Valley (BOI19_valley) C++14
36 / 100
 3000 ms 18572 KB 
//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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 4 ms 2764 KB Output is correct
3 Correct 4 ms 2892 KB Output is correct
4 Correct 4 ms 2892 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 4 ms 2764 KB Output is correct
3 Correct 4 ms 2892 KB Output is correct
4 Correct 4 ms 2892 KB Output is correct
5 Correct 3 ms 2952 KB Output is correct
6 Correct 2 ms 2892 KB Output is correct
7 Correct 2 ms 2944 KB Output is correct
8 Correct 2 ms 2892 KB Output is correct
9 Correct 2 ms 2892 KB Output is correct
10 Correct 4 ms 2892 KB Output is correct
11 Correct 2 ms 2892 KB Output is correct
12 Correct 3 ms 2892 KB Output is correct
13 Correct 6 ms 2992 KB Output is correct
14 Correct 4 ms 2892 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 18572 KB Output is correct
2 Correct 363 ms 18176 KB Output is correct
3 Execution timed out 3088 ms 18000 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 4 ms 2764 KB Output is correct
3 Correct 4 ms 2892 KB Output is correct
4 Correct 4 ms 2892 KB Output is correct
5 Correct 3 ms 2952 KB Output is correct
6 Correct 2 ms 2892 KB Output is correct
7 Correct 2 ms 2944 KB Output is correct
8 Correct 2 ms 2892 KB Output is correct
9 Correct 2 ms 2892 KB Output is correct
10 Correct 4 ms 2892 KB Output is correct
11 Correct 2 ms 2892 KB Output is correct
12 Correct 3 ms 2892 KB Output is correct
13 Correct 6 ms 2992 KB Output is correct
14 Correct 4 ms 2892 KB Output is correct
15 Correct 240 ms 18572 KB Output is correct
16 Correct 363 ms 18176 KB Output is correct
17 Execution timed out 3088 ms 18000 KB Time limit exceeded
18 Halted 0 ms 0 KB -