#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx,avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define rep(i,l,r) for(int i = (l); i < r; i++)
#define per(i,r,l) for(int i = (r); i >= l; i--)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define ss second
const ll mod = 1e9 + 7, maxn = 1e5 + 5, lg = 19, inf = 1e18 + 5;
int st[maxn], en[maxn], par[maxn][lg], t, h[maxn];
ll dp[maxn][lg], val[maxn][lg];
vector<pp> adj[maxn];
bool shop[maxn];
pp edge[maxn];
void dfs(int r, int p){
par[r][0] = p;
st[r] = t++;
dp[r][0] = (!shop[r])*inf;
for(pp c: adj[r]) if(c.ff != p){
h[c.ff] = h[r] + 1;
dfs(c.ff, r);
val[c.ff][0] = c.ss;
dp[r][0] = min(dp[r][0], dp[c.ff][0] + c.ss);
}
en[r] = t;
}
bool chkPar(int u, int p){
return st[p] <= st[u] && en[p] >= en[u];
}
int main(){
cin.tie(0) -> sync_with_stdio(false);
// freopen("input.txt", "r", stdin);
int n, s, q, e; cin >> n >> s >> q >> e; e--;
rep(i,0,n-1){
int u, v, w; cin >> u >> v >> w; u--, v--;
adj[u].pb({v, w});
adj[v].pb({u, w});
edge[i] = {u, v};
}
rep(i,0,s){
int t; cin >> t; t--;
shop[t] = true;
}
dfs(e, e);
rep(i,0,n-1){
if(!chkPar(edge[i].ff, edge[i].ss)){
swap(edge[i].ff, edge[i].ss);
}
}
rep(k,1,lg){
rep(i,0,n){
par[i][k] = par[par[i][k-1]][k-1];
dp[i][k] = min(dp[i][k-1], dp[par[i][k-1]][k-1] + val[i][k-1]);
val[i][k] = val[i][k-1] + val[par[i][k-1]][k-1];
}
}
while(q--){
int e, r; cin >> e >> r; e--, r--;
int u = edge[e].ff;
if(!chkPar(r, u)){
cout << "escaped\n";
}else{
int d = h[r] - h[u] + 1;
ll ans = inf, cr = 0;
rep(k,0,lg){
if(d>>k&1){
ans = min(ans, cr + dp[r][k]);
cr += val[r][k];
r = par[r][k];
}
}
if(ans == inf) cout << "oo\n";
else cout << ans << '\n';
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2764 KB |
Output is correct |
2 |
Correct |
4 ms |
2896 KB |
Output is correct |
3 |
Correct |
3 ms |
2824 KB |
Output is correct |
4 |
Correct |
3 ms |
2768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2764 KB |
Output is correct |
2 |
Correct |
4 ms |
2896 KB |
Output is correct |
3 |
Correct |
3 ms |
2824 KB |
Output is correct |
4 |
Correct |
3 ms |
2768 KB |
Output is correct |
5 |
Correct |
4 ms |
3080 KB |
Output is correct |
6 |
Correct |
3 ms |
3152 KB |
Output is correct |
7 |
Correct |
3 ms |
3080 KB |
Output is correct |
8 |
Correct |
3 ms |
3152 KB |
Output is correct |
9 |
Correct |
2 ms |
3152 KB |
Output is correct |
10 |
Correct |
2 ms |
3152 KB |
Output is correct |
11 |
Correct |
3 ms |
3156 KB |
Output is correct |
12 |
Correct |
2 ms |
3152 KB |
Output is correct |
13 |
Correct |
3 ms |
3152 KB |
Output is correct |
14 |
Correct |
2 ms |
3204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
174 ms |
50316 KB |
Output is correct |
2 |
Correct |
231 ms |
49988 KB |
Output is correct |
3 |
Correct |
194 ms |
49864 KB |
Output is correct |
4 |
Correct |
201 ms |
51684 KB |
Output is correct |
5 |
Correct |
176 ms |
51816 KB |
Output is correct |
6 |
Correct |
241 ms |
53752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2764 KB |
Output is correct |
2 |
Correct |
4 ms |
2896 KB |
Output is correct |
3 |
Correct |
3 ms |
2824 KB |
Output is correct |
4 |
Correct |
3 ms |
2768 KB |
Output is correct |
5 |
Correct |
4 ms |
3080 KB |
Output is correct |
6 |
Correct |
3 ms |
3152 KB |
Output is correct |
7 |
Correct |
3 ms |
3080 KB |
Output is correct |
8 |
Correct |
3 ms |
3152 KB |
Output is correct |
9 |
Correct |
2 ms |
3152 KB |
Output is correct |
10 |
Correct |
2 ms |
3152 KB |
Output is correct |
11 |
Correct |
3 ms |
3156 KB |
Output is correct |
12 |
Correct |
2 ms |
3152 KB |
Output is correct |
13 |
Correct |
3 ms |
3152 KB |
Output is correct |
14 |
Correct |
2 ms |
3204 KB |
Output is correct |
15 |
Correct |
174 ms |
50316 KB |
Output is correct |
16 |
Correct |
231 ms |
49988 KB |
Output is correct |
17 |
Correct |
194 ms |
49864 KB |
Output is correct |
18 |
Correct |
201 ms |
51684 KB |
Output is correct |
19 |
Correct |
176 ms |
51816 KB |
Output is correct |
20 |
Correct |
241 ms |
53752 KB |
Output is correct |
21 |
Correct |
154 ms |
49716 KB |
Output is correct |
22 |
Correct |
207 ms |
49300 KB |
Output is correct |
23 |
Correct |
197 ms |
49236 KB |
Output is correct |
24 |
Correct |
205 ms |
51224 KB |
Output is correct |
25 |
Correct |
213 ms |
54128 KB |
Output is correct |
26 |
Correct |
155 ms |
49804 KB |
Output is correct |
27 |
Correct |
154 ms |
49384 KB |
Output is correct |
28 |
Correct |
175 ms |
49292 KB |
Output is correct |
29 |
Correct |
189 ms |
50788 KB |
Output is correct |
30 |
Correct |
205 ms |
52204 KB |
Output is correct |
31 |
Correct |
194 ms |
49860 KB |
Output is correct |
32 |
Correct |
200 ms |
49480 KB |
Output is correct |
33 |
Correct |
168 ms |
49548 KB |
Output is correct |
34 |
Correct |
194 ms |
51272 KB |
Output is correct |
35 |
Correct |
217 ms |
54060 KB |
Output is correct |
36 |
Correct |
184 ms |
51496 KB |
Output is correct |