#include <bits/stdc++.h>
#define int long long
using namespace std;
const int nmax = 1e5 + 5, nbit = 17, inf = 2e16;
using pii = pair<int,int>;
vector<pii> edg, g[nmax];
int inp, occ[nmax], h[nmax], depth[nmax], pin[nmax], pout[nmax], p[nmax][nbit], mval[nmax][nbit];
vector<int> preorder;
int dfs(int node, int f) {
preorder.push_back(node);
pin[node] = inp++;
p[node][0] = f;
int mn = inf;
depth[node] += depth[f], h[node] = h[f] + 1;
for(auto [x, w] : g[node])
if(x != f) depth[x] = w, mn = min(dfs(x, node), mn);
if(occ[node])
mn = depth[node];
if(mn == inf)
mval[node][0] = inf;
else
mval[node][0] = mn - depth[node];
pout[node] = inp - 1;
//cerr << node << ' ' << depth[node] << ' ' << mn << '\n';
return mn;
}
bool isanc(int f, int node) {
return pin[f] <= pin[node] && pout[node] <= pout[f];
}
signed main() {
int n, q, s, root;
cin >> n >> s >> q >> root;
for(int i = 1, a, b, w; i < n; i++) {
cin >> a >> b >> w;
g[a].push_back({b, w});
g[b].push_back({a, w});
edg.push_back({a, b});
}
for(int i = 0, x; i < s; i++) cin >> x, occ[x] = 1;
dfs(root, root);
for(auto &[a, b] : edg) if(isanc(b, a)) swap(a, b);
for(auto x : preorder) {
for(int i = 1; i < nbit; i++) {
p[x][i] = p[p[x][i - 1]][i - 1];
mval[x][i] = min(mval[x][i - 1], depth[x] - depth[p[x][i - 1]] + mval[p[x][i - 1]][i - 1]);
}
}
for(int tc = 0, node, jusqu; tc < q; tc++) {
cin >> jusqu >> node;
//cout << jusqu << ' ' << edg[jusqu - 1].first << ' ' << edg[jusqu - 1].second << '\n';
if(!isanc(edg[--jusqu].second, node))
cout << "escaped\n";
else {
jusqu = edg[jusqu].first;
//cout << node << ' ' << jusqu << '\n';
int mn = inf, total = 0, diff = h[node] - h[jusqu];
for(int i = nbit - 1; i >= 0; i--) {
if((1 << i) & diff) {
mn = min(total + mval[node][i], mn);
total += depth[node] - depth[p[node][i]];
node = p[node][i];
}
}
if(mn >= inf / 2)
cout << "oo\n";
else
cout << mn << '\n';
}
}
}
Compilation message
valley.cpp: In function 'long long int dfs(long long int, long long int)':
valley.cpp:17:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
17 | for(auto [x, w] : g[node])
| ^
valley.cpp: In function 'int main()':
valley.cpp:45:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
45 | for(auto &[a, b] : edg) if(isanc(b, a)) swap(a, b);
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
2772 KB |
Output is correct |
2 |
Correct |
17 ms |
2772 KB |
Output is correct |
3 |
Correct |
17 ms |
2796 KB |
Output is correct |
4 |
Correct |
18 ms |
2832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
2772 KB |
Output is correct |
2 |
Correct |
17 ms |
2772 KB |
Output is correct |
3 |
Correct |
17 ms |
2796 KB |
Output is correct |
4 |
Correct |
18 ms |
2832 KB |
Output is correct |
5 |
Correct |
5 ms |
3028 KB |
Output is correct |
6 |
Correct |
4 ms |
3028 KB |
Output is correct |
7 |
Correct |
5 ms |
3028 KB |
Output is correct |
8 |
Correct |
4 ms |
3028 KB |
Output is correct |
9 |
Correct |
5 ms |
3028 KB |
Output is correct |
10 |
Correct |
4 ms |
3120 KB |
Output is correct |
11 |
Correct |
4 ms |
3056 KB |
Output is correct |
12 |
Correct |
5 ms |
3028 KB |
Output is correct |
13 |
Correct |
5 ms |
3056 KB |
Output is correct |
14 |
Correct |
4 ms |
3028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
368 ms |
46100 KB |
Output is correct |
2 |
Correct |
369 ms |
46192 KB |
Output is correct |
3 |
Correct |
371 ms |
46136 KB |
Output is correct |
4 |
Correct |
409 ms |
47796 KB |
Output is correct |
5 |
Correct |
365 ms |
47796 KB |
Output is correct |
6 |
Correct |
416 ms |
49540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
2772 KB |
Output is correct |
2 |
Correct |
17 ms |
2772 KB |
Output is correct |
3 |
Correct |
17 ms |
2796 KB |
Output is correct |
4 |
Correct |
18 ms |
2832 KB |
Output is correct |
5 |
Correct |
5 ms |
3028 KB |
Output is correct |
6 |
Correct |
4 ms |
3028 KB |
Output is correct |
7 |
Correct |
5 ms |
3028 KB |
Output is correct |
8 |
Correct |
4 ms |
3028 KB |
Output is correct |
9 |
Correct |
5 ms |
3028 KB |
Output is correct |
10 |
Correct |
4 ms |
3120 KB |
Output is correct |
11 |
Correct |
4 ms |
3056 KB |
Output is correct |
12 |
Correct |
5 ms |
3028 KB |
Output is correct |
13 |
Correct |
5 ms |
3056 KB |
Output is correct |
14 |
Correct |
4 ms |
3028 KB |
Output is correct |
15 |
Correct |
368 ms |
46100 KB |
Output is correct |
16 |
Correct |
369 ms |
46192 KB |
Output is correct |
17 |
Correct |
371 ms |
46136 KB |
Output is correct |
18 |
Correct |
409 ms |
47796 KB |
Output is correct |
19 |
Correct |
365 ms |
47796 KB |
Output is correct |
20 |
Correct |
416 ms |
49540 KB |
Output is correct |
21 |
Correct |
327 ms |
44856 KB |
Output is correct |
22 |
Correct |
332 ms |
44728 KB |
Output is correct |
23 |
Correct |
347 ms |
44852 KB |
Output is correct |
24 |
Correct |
367 ms |
46636 KB |
Output is correct |
25 |
Correct |
384 ms |
49200 KB |
Output is correct |
26 |
Correct |
329 ms |
45216 KB |
Output is correct |
27 |
Correct |
336 ms |
44992 KB |
Output is correct |
28 |
Correct |
359 ms |
45188 KB |
Output is correct |
29 |
Correct |
370 ms |
46380 KB |
Output is correct |
30 |
Correct |
380 ms |
47812 KB |
Output is correct |
31 |
Correct |
333 ms |
45660 KB |
Output is correct |
32 |
Correct |
347 ms |
45604 KB |
Output is correct |
33 |
Correct |
351 ms |
45852 KB |
Output is correct |
34 |
Correct |
415 ms |
47344 KB |
Output is correct |
35 |
Correct |
389 ms |
49732 KB |
Output is correct |
36 |
Correct |
362 ms |
47332 KB |
Output is correct |