#include <bits/stdc++.h>
#define len first
#define node second
#define pii pair<ll, ll>
typedef long long ll;
const ll MOD = 1000000007LL;
const ll INF = 1e15;
using namespace std;
struct edge {
ll u, v, w, id;
};
ll n, s, q, E, x, y, ans, tmp;
bool c[100010];
ll t, up[20][100010], tin[100010], tout[100010], dep[100010];
ll dp[100010], val[20][100010];
edge e[100010];
vector<pii> a[100010];
void dfs(ll x, ll p, ll dis) {
tin[x] = ++t;
dp[x] = (c[x]? 0: INF);
dep[x] = dis;
up[0][x] = p;
for (int i = 1; i <= 18; i++) up[i][x] = up[i-1][up[i-1][x]];
for (auto i: a[x]) {
if (i.node == p) continue;
dfs(i.node, x, dis+i.len);
dp[x] = min(dp[x], dp[i.node]+i.len);
}
tout[x] = ++t;
}
void dfs2(ll x, ll p) {
val[0][x] = dp[x]-dep[x];
for (int i = 1; i <= 18; i++) val[i][x] = min(val[i-1][x], val[i-1][up[i-1][x]]);
for (auto i: a[x]) {
if (i.node == p) continue;
dfs2(i.node, x);
}
}
bool isa(ll x, ll y) {
return tin[x] <= tin[y] && tout[y] <= tout[x];
}
int main() {
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
cin >> n >> s >> q >> E;
for (int i = 1; i < n; i++) {
cin >> e[i].u >> e[i].v >> e[i].w;
a[e[i].u].push_back({e[i].w, e[i].v});
a[e[i].v].push_back({e[i].w, e[i].u});
e[i].id = i;
}
for (int i = 1; i <= n; i++) c[i] = 0;
for (int i = 1; i <= s; i++) {
cin >> x;
c[x] = 1;
}
t = 0;
dfs(E, E, 0);
dfs2(E, E);
while (q--) {
cin >> x >> y;
if (isa(e[x].v, e[x].u)) swap(e[x].u, e[x].v);
if (isa(e[x].v, y)) {
if (dp[e[x].v] == INF) cout << "oo\n";
else if (e[x].v == y) cout << dp[y] << "\n";
else {
ans = INF; tmp = y;
for (int i = 18; i >= 0; i--) {
if (!isa(up[i][y], e[x].v)) {
ans = min(ans, val[i][y]);
y = up[i][y];
}
}
ans = min(ans, val[1][y]);
cout << ans+dep[tmp] << "\n";
}
}
else cout << "escaped\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
39516 KB |
Output is correct |
2 |
Correct |
7 ms |
39772 KB |
Output is correct |
3 |
Correct |
8 ms |
39772 KB |
Output is correct |
4 |
Correct |
7 ms |
39516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
39516 KB |
Output is correct |
2 |
Correct |
7 ms |
39772 KB |
Output is correct |
3 |
Correct |
8 ms |
39772 KB |
Output is correct |
4 |
Correct |
7 ms |
39516 KB |
Output is correct |
5 |
Correct |
5 ms |
39516 KB |
Output is correct |
6 |
Correct |
6 ms |
39516 KB |
Output is correct |
7 |
Correct |
6 ms |
39516 KB |
Output is correct |
8 |
Correct |
6 ms |
39512 KB |
Output is correct |
9 |
Correct |
6 ms |
39516 KB |
Output is correct |
10 |
Correct |
7 ms |
39516 KB |
Output is correct |
11 |
Correct |
7 ms |
39924 KB |
Output is correct |
12 |
Correct |
6 ms |
39516 KB |
Output is correct |
13 |
Correct |
7 ms |
39516 KB |
Output is correct |
14 |
Correct |
6 ms |
39516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
141 ms |
45492 KB |
Output is correct |
2 |
Correct |
151 ms |
48976 KB |
Output is correct |
3 |
Correct |
172 ms |
49472 KB |
Output is correct |
4 |
Correct |
207 ms |
51052 KB |
Output is correct |
5 |
Correct |
162 ms |
51280 KB |
Output is correct |
6 |
Correct |
205 ms |
53584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
39516 KB |
Output is correct |
2 |
Correct |
7 ms |
39772 KB |
Output is correct |
3 |
Correct |
8 ms |
39772 KB |
Output is correct |
4 |
Correct |
7 ms |
39516 KB |
Output is correct |
5 |
Correct |
5 ms |
39516 KB |
Output is correct |
6 |
Correct |
6 ms |
39516 KB |
Output is correct |
7 |
Correct |
6 ms |
39516 KB |
Output is correct |
8 |
Correct |
6 ms |
39512 KB |
Output is correct |
9 |
Correct |
6 ms |
39516 KB |
Output is correct |
10 |
Correct |
7 ms |
39516 KB |
Output is correct |
11 |
Correct |
7 ms |
39924 KB |
Output is correct |
12 |
Correct |
6 ms |
39516 KB |
Output is correct |
13 |
Correct |
7 ms |
39516 KB |
Output is correct |
14 |
Correct |
6 ms |
39516 KB |
Output is correct |
15 |
Correct |
141 ms |
45492 KB |
Output is correct |
16 |
Correct |
151 ms |
48976 KB |
Output is correct |
17 |
Correct |
172 ms |
49472 KB |
Output is correct |
18 |
Correct |
207 ms |
51052 KB |
Output is correct |
19 |
Correct |
162 ms |
51280 KB |
Output is correct |
20 |
Correct |
205 ms |
53584 KB |
Output is correct |
21 |
Correct |
128 ms |
48584 KB |
Output is correct |
22 |
Correct |
136 ms |
48564 KB |
Output is correct |
23 |
Correct |
149 ms |
48708 KB |
Output is correct |
24 |
Correct |
151 ms |
50980 KB |
Output is correct |
25 |
Correct |
180 ms |
53880 KB |
Output is correct |
26 |
Correct |
150 ms |
48788 KB |
Output is correct |
27 |
Correct |
134 ms |
48468 KB |
Output is correct |
28 |
Correct |
152 ms |
48836 KB |
Output is correct |
29 |
Correct |
185 ms |
50256 KB |
Output is correct |
30 |
Correct |
192 ms |
51732 KB |
Output is correct |
31 |
Correct |
149 ms |
48696 KB |
Output is correct |
32 |
Correct |
148 ms |
48720 KB |
Output is correct |
33 |
Correct |
158 ms |
48980 KB |
Output is correct |
34 |
Correct |
200 ms |
50820 KB |
Output is correct |
35 |
Correct |
184 ms |
53756 KB |
Output is correct |
36 |
Correct |
190 ms |
50872 KB |
Output is correct |