#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
#define ff first
#define ss second
#define pb push_back
#define int ll
const int oo = 1e18 + 7;
int n, s, q, e;
vector<array<int, 3>> adj[100001];
bool rem[100001], shop[100001];
int ans = oo; bool ok = 0;
int tin[100001], out[100001], timer;
int dep[100001], par[100001][20], mn[100001][20], sbmn[100001];
int dfs_euler(int v, int p) {
tin[v] = timer++; par[v][0] = p;
for(auto u : adj[v]) {
if(u[0] == p) continue;
dep[u[0]] = dep[v] + u[1];
sbmn[v] = min(sbmn[v], dfs_euler(u[0], v) + u[1]);
if(sbmn[u[0]] != oo)
mn[u[0]][0] = sbmn[u[0]]-dep[u[0]];
}
out[v] = timer - 1;
if(shop[v]) sbmn[v] = 0;
return sbmn[v];
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> s >> q >> e; e--; vector<ii> edges(n - 1);
fill(sbmn, sbmn + 100001, oo);
for(int l = 0; l < n; l++)
for(int i = 0; i < 20; i++)
mn[l][i] = oo;
for(int l = 0; l < n - 1; l++) {
int u, v, w; cin >> u >> v >> w; u--; v--;
adj[u].pb({v, w, l}); adj[v].pb({u, w, l});
edges[l] = {u, v};
}
for(int l = 0; l < s; l++) {
int u; cin >> u; u--; shop[u] = 1;
}
dep[e] = 0; dfs_euler(e, e); /// mn[e][0] = sbmn[e];
for(int l = 1; l < 20; l++)
for(int i = 0; i < n; i++){
par[i][l] = par[par[i][l - 1]][l - 1];
mn[i][l] = min(mn[i][l - 1], mn[par[i][l - 1]][l - 1]);
}
while(q--) {
int r, v; cin >> r >> v; r--; v--;
int to = edges[r].ff, from = edges[r].ss;
if(tin[to] < tin[from]) swap(to, from);
if(tin[to] <= tin[v] && tin[v] <= out[to]) {
int ans = oo, kk = v;
for (int i = 19; i >= 0; --i) {
if(dep[par[v][i]] >= dep[to]){
ans = min(ans, mn[v][i]);
v = par[v][i];
}
}
ans = min(ans, mn[v][0]);
if(ans == oo) cout << "oo\n";
else cout << ans + dep[kk] << "\n";
}
else cout << "escaped\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3596 KB |
Output is correct |
2 |
Correct |
4 ms |
3580 KB |
Output is correct |
3 |
Correct |
4 ms |
3668 KB |
Output is correct |
4 |
Correct |
4 ms |
3540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3596 KB |
Output is correct |
2 |
Correct |
4 ms |
3580 KB |
Output is correct |
3 |
Correct |
4 ms |
3668 KB |
Output is correct |
4 |
Correct |
4 ms |
3540 KB |
Output is correct |
5 |
Correct |
3 ms |
3924 KB |
Output is correct |
6 |
Correct |
3 ms |
3924 KB |
Output is correct |
7 |
Correct |
3 ms |
3968 KB |
Output is correct |
8 |
Correct |
3 ms |
3924 KB |
Output is correct |
9 |
Correct |
3 ms |
3924 KB |
Output is correct |
10 |
Correct |
3 ms |
3968 KB |
Output is correct |
11 |
Correct |
3 ms |
3840 KB |
Output is correct |
12 |
Correct |
3 ms |
3924 KB |
Output is correct |
13 |
Correct |
3 ms |
3924 KB |
Output is correct |
14 |
Correct |
3 ms |
3924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
195 ms |
49612 KB |
Output is correct |
2 |
Correct |
202 ms |
49640 KB |
Output is correct |
3 |
Correct |
181 ms |
49800 KB |
Output is correct |
4 |
Correct |
219 ms |
51736 KB |
Output is correct |
5 |
Correct |
169 ms |
51836 KB |
Output is correct |
6 |
Correct |
249 ms |
53952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3596 KB |
Output is correct |
2 |
Correct |
4 ms |
3580 KB |
Output is correct |
3 |
Correct |
4 ms |
3668 KB |
Output is correct |
4 |
Correct |
4 ms |
3540 KB |
Output is correct |
5 |
Correct |
3 ms |
3924 KB |
Output is correct |
6 |
Correct |
3 ms |
3924 KB |
Output is correct |
7 |
Correct |
3 ms |
3968 KB |
Output is correct |
8 |
Correct |
3 ms |
3924 KB |
Output is correct |
9 |
Correct |
3 ms |
3924 KB |
Output is correct |
10 |
Correct |
3 ms |
3968 KB |
Output is correct |
11 |
Correct |
3 ms |
3840 KB |
Output is correct |
12 |
Correct |
3 ms |
3924 KB |
Output is correct |
13 |
Correct |
3 ms |
3924 KB |
Output is correct |
14 |
Correct |
3 ms |
3924 KB |
Output is correct |
15 |
Correct |
195 ms |
49612 KB |
Output is correct |
16 |
Correct |
202 ms |
49640 KB |
Output is correct |
17 |
Correct |
181 ms |
49800 KB |
Output is correct |
18 |
Correct |
219 ms |
51736 KB |
Output is correct |
19 |
Correct |
169 ms |
51836 KB |
Output is correct |
20 |
Correct |
249 ms |
53952 KB |
Output is correct |
21 |
Correct |
150 ms |
48948 KB |
Output is correct |
22 |
Correct |
177 ms |
49032 KB |
Output is correct |
23 |
Correct |
222 ms |
49188 KB |
Output is correct |
24 |
Correct |
190 ms |
51308 KB |
Output is correct |
25 |
Correct |
218 ms |
54316 KB |
Output is correct |
26 |
Correct |
163 ms |
49064 KB |
Output is correct |
27 |
Correct |
183 ms |
49020 KB |
Output is correct |
28 |
Correct |
193 ms |
49380 KB |
Output is correct |
29 |
Correct |
235 ms |
50784 KB |
Output is correct |
30 |
Correct |
227 ms |
52432 KB |
Output is correct |
31 |
Correct |
166 ms |
49188 KB |
Output is correct |
32 |
Correct |
182 ms |
49232 KB |
Output is correct |
33 |
Correct |
198 ms |
49532 KB |
Output is correct |
34 |
Correct |
207 ms |
51396 KB |
Output is correct |
35 |
Correct |
236 ms |
54376 KB |
Output is correct |
36 |
Correct |
181 ms |
51532 KB |
Output is correct |