# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
672555 |
2022-12-16T15:33:21 Z |
_martynas |
Valley (BOI19_valley) |
C++11 |
|
248 ms |
50960 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
const int MOD = 1e9+7;
#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
const int MXN = 1e5+5;
const int MXK = 16;
const ll INF = 1e15;
int n, s, q, e;
vector<tuple<int, int, ll>> E = {{}};
vector<pil> adj[MXN];
bool shop[MXN];
int BL[MXK][MXN];
ll BL_w[MXK][MXN];
ll BL_dp[MXK][MXN];
int H[MXN];
ll dp[MXN];
void dfs(int u, int p) {
dp[u] = (shop[u] ? 0 : INF);
for(auto edge : adj[u]) {
int v = edge.F;
if(v == p) continue;
BL[0][v] = u;
BL_w[0][v] = edge.S;
H[v] = H[u]+1;
dfs(v, u);
dp[u] = min(dp[u], dp[v]+edge.S); // dp going down the subtree
}
}
int main() {
FASTIO();
cin >> n >> s >> q >> e;
for(int i = 0; i < n-1; i++) {
int a, b, w; cin >> a >> b >> w;
E.PB({a, b, w});
adj[a].PB({b, w});
adj[b].PB({a, w});
}
for(int i = 0; i < s; i++) {
int j; cin >> j; shop[j] = true;
}
dfs(e, -1);
BL[0][e] = e;
for(int i = 1; i <= n; i++) {
BL_dp[0][i] = min(dp[i], dp[BL[0][i]]+BL_w[0][i]);
}
for(int k = 1; k < MXK; k++) {
for(int i = 1; i <= n; i++) {
BL[k][i] = BL[k-1][BL[k-1][i]];
BL_w[k][i] = BL_w[k-1][i]+BL_w[k-1][BL[k-1][i]];
BL_dp[k][i] = min(BL_dp[k-1][i], BL_dp[k-1][BL[k-1][i]]+BL_w[k-1][i]);
}
}
for(int qq = 0; qq < q; qq++) {
int i, r; cin >> i >> r;
// 1. binary lift to check if i-th edge is the one needed to take to reach the root
// 2. if yes, check dp for minimal distance to shop(?)
int u = H[get<0>(E[i])] > H[get<1>(E[i])] ? get<0>(E[i]) : get<1>(E[i]);
if(H[r] < H[u]) {
cout << "escaped\n";
continue;
}
int v = r;
ll ans = dp[r];
ll curr = 0;
for(int k = MXK-1; k >= 0; k--)
while(H[BL[k][v]] >= H[u]) {
ans = min(ans, BL_dp[k][v]+curr);
curr += BL_w[k][v];
v = BL[k][v];
}
if(u != v) {
cout << "escaped\n";
continue;
}
if(ans >= INF) {
cout << "oo\n";
}
else {
cout << ans << "\n";
}
}
return 0;
}
/*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3028 KB |
Output is correct |
2 |
Correct |
4 ms |
3028 KB |
Output is correct |
3 |
Correct |
4 ms |
3068 KB |
Output is correct |
4 |
Correct |
4 ms |
3028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3028 KB |
Output is correct |
2 |
Correct |
4 ms |
3028 KB |
Output is correct |
3 |
Correct |
4 ms |
3068 KB |
Output is correct |
4 |
Correct |
4 ms |
3028 KB |
Output is correct |
5 |
Correct |
2 ms |
3328 KB |
Output is correct |
6 |
Correct |
2 ms |
3284 KB |
Output is correct |
7 |
Correct |
3 ms |
3284 KB |
Output is correct |
8 |
Correct |
2 ms |
3284 KB |
Output is correct |
9 |
Correct |
3 ms |
3284 KB |
Output is correct |
10 |
Correct |
4 ms |
3284 KB |
Output is correct |
11 |
Correct |
4 ms |
3284 KB |
Output is correct |
12 |
Correct |
3 ms |
3284 KB |
Output is correct |
13 |
Correct |
4 ms |
3332 KB |
Output is correct |
14 |
Correct |
3 ms |
3324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
42552 KB |
Output is correct |
2 |
Correct |
127 ms |
46184 KB |
Output is correct |
3 |
Correct |
154 ms |
46492 KB |
Output is correct |
4 |
Correct |
187 ms |
48328 KB |
Output is correct |
5 |
Correct |
190 ms |
48488 KB |
Output is correct |
6 |
Correct |
248 ms |
50616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3028 KB |
Output is correct |
2 |
Correct |
4 ms |
3028 KB |
Output is correct |
3 |
Correct |
4 ms |
3068 KB |
Output is correct |
4 |
Correct |
4 ms |
3028 KB |
Output is correct |
5 |
Correct |
2 ms |
3328 KB |
Output is correct |
6 |
Correct |
2 ms |
3284 KB |
Output is correct |
7 |
Correct |
3 ms |
3284 KB |
Output is correct |
8 |
Correct |
2 ms |
3284 KB |
Output is correct |
9 |
Correct |
3 ms |
3284 KB |
Output is correct |
10 |
Correct |
4 ms |
3284 KB |
Output is correct |
11 |
Correct |
4 ms |
3284 KB |
Output is correct |
12 |
Correct |
3 ms |
3284 KB |
Output is correct |
13 |
Correct |
4 ms |
3332 KB |
Output is correct |
14 |
Correct |
3 ms |
3324 KB |
Output is correct |
15 |
Correct |
113 ms |
42552 KB |
Output is correct |
16 |
Correct |
127 ms |
46184 KB |
Output is correct |
17 |
Correct |
154 ms |
46492 KB |
Output is correct |
18 |
Correct |
187 ms |
48328 KB |
Output is correct |
19 |
Correct |
190 ms |
48488 KB |
Output is correct |
20 |
Correct |
248 ms |
50616 KB |
Output is correct |
21 |
Correct |
106 ms |
45816 KB |
Output is correct |
22 |
Correct |
123 ms |
45664 KB |
Output is correct |
23 |
Correct |
144 ms |
45848 KB |
Output is correct |
24 |
Correct |
168 ms |
47968 KB |
Output is correct |
25 |
Correct |
215 ms |
50960 KB |
Output is correct |
26 |
Correct |
112 ms |
45900 KB |
Output is correct |
27 |
Correct |
133 ms |
45696 KB |
Output is correct |
28 |
Correct |
151 ms |
45896 KB |
Output is correct |
29 |
Correct |
151 ms |
47352 KB |
Output is correct |
30 |
Correct |
242 ms |
49160 KB |
Output is correct |
31 |
Correct |
131 ms |
46000 KB |
Output is correct |
32 |
Correct |
152 ms |
45764 KB |
Output is correct |
33 |
Correct |
149 ms |
46032 KB |
Output is correct |
34 |
Correct |
156 ms |
47972 KB |
Output is correct |
35 |
Correct |
210 ms |
50840 KB |
Output is correct |
36 |
Correct |
162 ms |
48008 KB |
Output is correct |