#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5, INF = 1e18;
vector<array<int, 2>> g[MAXN];
array<int, 18> p [MAXN], m[MAXN];
vector<int> s(MAXN, INF), d(MAXN), depth(MAXN), t0(MAXN), t1(MAXN);
int dfsTimer = 0;
int dfs0(int u, int par, int dist){
d[u] = dist;
t0[u] = dfsTimer++;
for(auto &e : g[u]) if(e[0] != par) s[u] = min(s[u], dfs0(e[0], u, dist + e[1]) + e[1]);
t1[u] = dfsTimer++;
return s[u];
}
void dfs1(int u, int par, int dep){
depth[u] = dep;
p[u][0] = par;
m[u][0] = min(s[u] - d[u], s[par] - d[par]);
for(int i=0; i<17; ++i){
m[u][i+1] = min(m[u][i], m[p[u][i]][i]);
p[u][i+1] = p[p[u][i]][i];
}
for(auto &e : g[u]) if(e[0] != par) dfs1(e[0], u, dep + 1);
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n, shops, q, root, x, y, z; cin >> n >> shops >> q >> root;
array<int, 2> edges[n-1];
for(int i=1; i<n; ++i){
cin >> x >> y >> z; --x, --y;
g[x].push_back({y, z});
g[y].push_back({x, z});
edges[i-1] = {x, y};
}
while(shops--) cin >> x, s[x-1] = 0;
--root;
dfs0(root, root, 0);
dfs1(root, root, 0);
while(q--){
cin >> x >> y; --x, --y;
x = edges[x][p[edges[x][1]][0] == edges[x][0]];
if(t0[x] <= t0[y] and t1[y] <= t1[x]){
int res = s[y], j = d[y];
int diff = depth[y] - depth[x];
for(int i=0; i<18; ++i) if(diff & (1<<i)) res = min(res, m[y][i]+j), y = p[y][i];
if(res >= INF) cout << "oo\n";
else cout << res << '\n';
}else cout << "escaped\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
10076 KB |
Output is correct |
2 |
Correct |
5 ms |
10076 KB |
Output is correct |
3 |
Correct |
4 ms |
10076 KB |
Output is correct |
4 |
Correct |
5 ms |
10076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
10076 KB |
Output is correct |
2 |
Correct |
5 ms |
10076 KB |
Output is correct |
3 |
Correct |
4 ms |
10076 KB |
Output is correct |
4 |
Correct |
5 ms |
10076 KB |
Output is correct |
5 |
Correct |
3 ms |
10332 KB |
Output is correct |
6 |
Correct |
4 ms |
10332 KB |
Output is correct |
7 |
Correct |
4 ms |
10276 KB |
Output is correct |
8 |
Correct |
4 ms |
10332 KB |
Output is correct |
9 |
Correct |
3 ms |
10328 KB |
Output is correct |
10 |
Correct |
4 ms |
10332 KB |
Output is correct |
11 |
Correct |
4 ms |
10332 KB |
Output is correct |
12 |
Correct |
4 ms |
10328 KB |
Output is correct |
13 |
Correct |
4 ms |
10332 KB |
Output is correct |
14 |
Correct |
4 ms |
10352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
101 ms |
45904 KB |
Output is correct |
2 |
Correct |
110 ms |
45912 KB |
Output is correct |
3 |
Correct |
133 ms |
46024 KB |
Output is correct |
4 |
Correct |
127 ms |
47440 KB |
Output is correct |
5 |
Correct |
111 ms |
47720 KB |
Output is correct |
6 |
Correct |
137 ms |
49488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
10076 KB |
Output is correct |
2 |
Correct |
5 ms |
10076 KB |
Output is correct |
3 |
Correct |
4 ms |
10076 KB |
Output is correct |
4 |
Correct |
5 ms |
10076 KB |
Output is correct |
5 |
Correct |
3 ms |
10332 KB |
Output is correct |
6 |
Correct |
4 ms |
10332 KB |
Output is correct |
7 |
Correct |
4 ms |
10276 KB |
Output is correct |
8 |
Correct |
4 ms |
10332 KB |
Output is correct |
9 |
Correct |
3 ms |
10328 KB |
Output is correct |
10 |
Correct |
4 ms |
10332 KB |
Output is correct |
11 |
Correct |
4 ms |
10332 KB |
Output is correct |
12 |
Correct |
4 ms |
10328 KB |
Output is correct |
13 |
Correct |
4 ms |
10332 KB |
Output is correct |
14 |
Correct |
4 ms |
10352 KB |
Output is correct |
15 |
Correct |
101 ms |
45904 KB |
Output is correct |
16 |
Correct |
110 ms |
45912 KB |
Output is correct |
17 |
Correct |
133 ms |
46024 KB |
Output is correct |
18 |
Correct |
127 ms |
47440 KB |
Output is correct |
19 |
Correct |
111 ms |
47720 KB |
Output is correct |
20 |
Correct |
137 ms |
49488 KB |
Output is correct |
21 |
Correct |
93 ms |
45400 KB |
Output is correct |
22 |
Correct |
107 ms |
45364 KB |
Output is correct |
23 |
Correct |
108 ms |
45492 KB |
Output is correct |
24 |
Correct |
136 ms |
47540 KB |
Output is correct |
25 |
Correct |
119 ms |
49744 KB |
Output is correct |
26 |
Correct |
96 ms |
45396 KB |
Output is correct |
27 |
Correct |
100 ms |
45396 KB |
Output is correct |
28 |
Correct |
108 ms |
45400 KB |
Output is correct |
29 |
Correct |
119 ms |
46636 KB |
Output is correct |
30 |
Correct |
122 ms |
47956 KB |
Output is correct |
31 |
Correct |
101 ms |
45604 KB |
Output is correct |
32 |
Correct |
104 ms |
45512 KB |
Output is correct |
33 |
Correct |
110 ms |
45652 KB |
Output is correct |
34 |
Correct |
121 ms |
47296 KB |
Output is correct |
35 |
Correct |
122 ms |
49692 KB |
Output is correct |
36 |
Correct |
114 ms |
47144 KB |
Output is correct |