#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
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]){ //ancestor
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" nl;
else cout << res nl;
}else cout << "escaped" nl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
6604 KB |
Output is correct |
2 |
Correct |
7 ms |
6736 KB |
Output is correct |
3 |
Correct |
6 ms |
6732 KB |
Output is correct |
4 |
Correct |
6 ms |
6732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
6604 KB |
Output is correct |
2 |
Correct |
7 ms |
6736 KB |
Output is correct |
3 |
Correct |
6 ms |
6732 KB |
Output is correct |
4 |
Correct |
6 ms |
6732 KB |
Output is correct |
5 |
Correct |
4 ms |
6864 KB |
Output is correct |
6 |
Correct |
5 ms |
6860 KB |
Output is correct |
7 |
Correct |
6 ms |
6988 KB |
Output is correct |
8 |
Correct |
4 ms |
6860 KB |
Output is correct |
9 |
Correct |
5 ms |
6860 KB |
Output is correct |
10 |
Correct |
5 ms |
6988 KB |
Output is correct |
11 |
Correct |
5 ms |
6860 KB |
Output is correct |
12 |
Correct |
5 ms |
6924 KB |
Output is correct |
13 |
Correct |
5 ms |
6860 KB |
Output is correct |
14 |
Correct |
5 ms |
6968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
175 ms |
42340 KB |
Output is correct |
2 |
Correct |
193 ms |
41944 KB |
Output is correct |
3 |
Correct |
220 ms |
42216 KB |
Output is correct |
4 |
Correct |
219 ms |
43664 KB |
Output is correct |
5 |
Correct |
207 ms |
43796 KB |
Output is correct |
6 |
Correct |
238 ms |
45444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
6604 KB |
Output is correct |
2 |
Correct |
7 ms |
6736 KB |
Output is correct |
3 |
Correct |
6 ms |
6732 KB |
Output is correct |
4 |
Correct |
6 ms |
6732 KB |
Output is correct |
5 |
Correct |
4 ms |
6864 KB |
Output is correct |
6 |
Correct |
5 ms |
6860 KB |
Output is correct |
7 |
Correct |
6 ms |
6988 KB |
Output is correct |
8 |
Correct |
4 ms |
6860 KB |
Output is correct |
9 |
Correct |
5 ms |
6860 KB |
Output is correct |
10 |
Correct |
5 ms |
6988 KB |
Output is correct |
11 |
Correct |
5 ms |
6860 KB |
Output is correct |
12 |
Correct |
5 ms |
6924 KB |
Output is correct |
13 |
Correct |
5 ms |
6860 KB |
Output is correct |
14 |
Correct |
5 ms |
6968 KB |
Output is correct |
15 |
Correct |
175 ms |
42340 KB |
Output is correct |
16 |
Correct |
193 ms |
41944 KB |
Output is correct |
17 |
Correct |
220 ms |
42216 KB |
Output is correct |
18 |
Correct |
219 ms |
43664 KB |
Output is correct |
19 |
Correct |
207 ms |
43796 KB |
Output is correct |
20 |
Correct |
238 ms |
45444 KB |
Output is correct |
21 |
Correct |
168 ms |
42216 KB |
Output is correct |
22 |
Correct |
169 ms |
41928 KB |
Output is correct |
23 |
Correct |
177 ms |
42152 KB |
Output is correct |
24 |
Correct |
206 ms |
43972 KB |
Output is correct |
25 |
Correct |
235 ms |
49604 KB |
Output is correct |
26 |
Correct |
170 ms |
45328 KB |
Output is correct |
27 |
Correct |
185 ms |
45276 KB |
Output is correct |
28 |
Correct |
195 ms |
45400 KB |
Output is correct |
29 |
Correct |
212 ms |
46644 KB |
Output is correct |
30 |
Correct |
238 ms |
48144 KB |
Output is correct |
31 |
Correct |
161 ms |
45424 KB |
Output is correct |
32 |
Correct |
176 ms |
45336 KB |
Output is correct |
33 |
Correct |
193 ms |
45636 KB |
Output is correct |
34 |
Correct |
227 ms |
47172 KB |
Output is correct |
35 |
Correct |
231 ms |
49500 KB |
Output is correct |
36 |
Correct |
216 ms |
47048 KB |
Output is correct |