이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//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';
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |