#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
#define ll long long
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }
vector<vector<pair<int, int>>> adj;
vector<int> tin, tout, par, dep;
vector<ll int> dist, dp1;
vector<bool> shop;
int timer = 0;
void dfs(int u, int p, ll int dis, int d = 0) {
dist[u] = dis;
tin[u] = timer++;
par[u] = p;
dep[u] = d;
for (auto [v, w] : adj[u]) {
if (v == p) continue;
dfs(v, u, dis + w, d + 1);
}
if (shop[u]) dp1[u] = dist[u];
else dp1[u] = 1e18;
for (auto [v, wt] : adj[u]) {
if (v == p) continue;
dp1[u] = min(dp1[u], dp1[v]);
}
tout[u] = timer - 1;
}
bool is_acc(int acc, int child) {
if (acc == child) return 1;
return tin[acc] < tin[child] && tin[child] <= tout[acc];
}
void solve() {
int n, s, q, e; cin >> n >> s >> q >> e;
adj.resize(n);
dp1.resize(n);
tin.resize(n);
tout.resize(n);
dist.resize(n);
shop.resize(n);
par.resize(n);
dep.resize(n);
fill(all(dp1), 1e18);
vector<pair<pair<int, int>, int>> edges;
for (int i = 0; i < n - 1; i++) {
int a, b; cin >> a >> b;
int c; cin >> c;
a--, b--;
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
edges.emplace_back(make_pair(a, b), c);
}
for (int i = 0; i < s; i++) {
int a; cin >> a;
shop[a - 1] = 1;
}
// e is the root
dfs(e - 1, e - 1, 0);
for (int i = 0; i < n; i++) {
dp1[i] = dp1[i] - 2 * dist[i];
}
const int LOG = 20;
vector<vector<ll int>> jumpNode(n, vector<ll int>(20)), jumpDP(n, vector<ll int>(20));
for (int i = 0; i < n; i++) {
jumpNode[i][0] = par[i];
jumpDP[i][0] = dp1[i];
}
for (int i = 1; i < LOG; i++) {
for (int j = 0; j < n; j++) {
jumpNode[j][i] = jumpNode[jumpNode[j][i - 1]][i - 1];
jumpDP[j][i] = min(jumpDP[j][i - 1], jumpDP[jumpNode[j][i - 1]][i - 1]); // somewhat like sparse tables
}
}
auto query = [&](int u, int k) -> ll int {
int pow = LOG;
ll int res = 1e18;
while (k > 0) {
while (k < (1 << pow)) pow--;
res = min(res, jumpDP[u][pow]);
u = jumpNode[u][pow];
k -= (1 << pow);
}
return res;
};
while (q--) {
int a, b; cin >> a >> b;
a--, b--;
pair<int, int> edge = edges[a].first;
if (is_acc(edge.first, b) && is_acc(edge.second, b)) {
int one = edge.first;
if (dist[one] < dist[edge.second]) {
one = edge.second;
}
ll int res = query(b, dep[b] - dep[one] + 1);
if (res >= 1e16) {
cout << "oo" << endl;
} else {
cout << res + dist[b] << endl;
}
} else {
cout << "escaped" << endl;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T--)
solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
4 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
4 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Correct |
2 ms |
724 KB |
Output is correct |
12 |
Correct |
3 ms |
724 KB |
Output is correct |
13 |
Correct |
2 ms |
724 KB |
Output is correct |
14 |
Correct |
2 ms |
852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
201 ms |
50608 KB |
Output is correct |
2 |
Correct |
191 ms |
50284 KB |
Output is correct |
3 |
Correct |
197 ms |
50240 KB |
Output is correct |
4 |
Correct |
225 ms |
52516 KB |
Output is correct |
5 |
Correct |
218 ms |
52548 KB |
Output is correct |
6 |
Correct |
277 ms |
54816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
4 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Correct |
2 ms |
724 KB |
Output is correct |
12 |
Correct |
3 ms |
724 KB |
Output is correct |
13 |
Correct |
2 ms |
724 KB |
Output is correct |
14 |
Correct |
2 ms |
852 KB |
Output is correct |
15 |
Correct |
201 ms |
50608 KB |
Output is correct |
16 |
Correct |
191 ms |
50284 KB |
Output is correct |
17 |
Correct |
197 ms |
50240 KB |
Output is correct |
18 |
Correct |
225 ms |
52516 KB |
Output is correct |
19 |
Correct |
218 ms |
52548 KB |
Output is correct |
20 |
Correct |
277 ms |
54816 KB |
Output is correct |
21 |
Correct |
189 ms |
50672 KB |
Output is correct |
22 |
Correct |
192 ms |
50432 KB |
Output is correct |
23 |
Correct |
226 ms |
50264 KB |
Output is correct |
24 |
Correct |
251 ms |
52776 KB |
Output is correct |
25 |
Correct |
263 ms |
56156 KB |
Output is correct |
26 |
Correct |
183 ms |
50728 KB |
Output is correct |
27 |
Correct |
191 ms |
50352 KB |
Output is correct |
28 |
Correct |
194 ms |
50404 KB |
Output is correct |
29 |
Correct |
243 ms |
52016 KB |
Output is correct |
30 |
Correct |
242 ms |
53648 KB |
Output is correct |
31 |
Correct |
171 ms |
50812 KB |
Output is correct |
32 |
Correct |
183 ms |
50448 KB |
Output is correct |
33 |
Correct |
185 ms |
50388 KB |
Output is correct |
34 |
Correct |
252 ms |
52560 KB |
Output is correct |
35 |
Correct |
234 ms |
55908 KB |
Output is correct |
36 |
Correct |
215 ms |
53256 KB |
Output is correct |