| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 898788 | vjudge1 | Valley (BOI19_valley) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define u_map unordered_map
#define int ll
const int maxn = 1e5 + 5, mod = 1e9 + 7;
vector<pii> adj[maxn], edg;
bool sho[maxn];
map<pii, int> va;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, s, q, e;
cin >> n >> s >> q >> e;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].pb({w, v});
adj[v].pb({w, u});
va[{u, v}] = w;
va[{v, u}] = w;
edg.pb({u, v});
}
for (int i = 1; i <= s; i++) {
int x;
cin >> x;
sho[x] = 1;
}
while (q--) {
int l, r;
cin >> l >> r;
if ((r <= l and e <= l) or (r > l and e > l)) {
cout << "escaped" << endl;
continue;
}
int ans1 = 0, ans2 = 0;
bool is1 = false, is2 = false;
for (int i = r; i >= max(1, l + 1); i--) {
if (sho[i]) {
is1 = true;
break;
}
ans1 += va[{i, i - 1}];
}
for (int i = r; i <= min({n, l}); i++) {
if (sho[i]) {
is2 = true;
break;
}
ans2 += va[{i, i + 1}];
}
if (!(is1 or is2)) {
cout << "oo" << endl;
} else {
cout << min(((is1 ^ 1) * mod) + ans1, ((is2 ^ 1) * mod) + ans2) << endl;
}
}
return 0;
}