# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
915598 |
2024-01-24T09:44:42 Z |
uped |
Valley (BOI19_valley) |
C++14 |
|
357 ms |
68660 KB |
#include <bits/stdc++.h>
#define DEBUG(x) cout << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
const ll MAXN = 1e5 + 1;
const ll INF = 1e18;
vector<pair<ll, ll>> adj[MAXN];
ll shop_in_subtree[MAXN];
ll tin[MAXN];
ll tout[MAXN];
ll depth[MAXN];
// destination, min(shop_in_subtree) on path to dst, dist_of_path
tuple<ll, ll, ll> jmp[20][MAXN];
bool is_shop[MAXN];
ll timer = 0;
void dfs(ll n, ll p = 0, ll pw = 0) {
depth[n] = depth[p] + 1;
tin[n] = timer++;
shop_in_subtree[n] = (is_shop[n] ? 0 : INF);
for (auto& [x, w] : adj[n]) {
if (x == p) continue;
dfs(x, n, w);
shop_in_subtree[n] = min(shop_in_subtree[x] + w, shop_in_subtree[n]);
}
jmp[0][n] = {p, shop_in_subtree[n], pw};
tout[n] = timer++;
}
int main() {
ll n, s, q, e;
cin >> n >> s >> q >> e;
vector<pair<ll, ll>> edges(n - 1);
for (ll i = 0; i < n - 1; ++i) {
ll a, b, w;
cin >> a >> b >> w;
adj[a].emplace_back(b, w);
adj[b].emplace_back(a, w);
edges[i] = {a, b};
}
for (ll i = 0; i < s; ++i) {
ll x;
cin >> x;
is_shop[x] = true;
}
dfs(e);
for (ll i = 1; i < 20; ++i) {
for (ll j = 1; j <= n; ++j) {
auto& [a, b, c] = jmp[i - 1][j];
auto& [x, y, z] = jmp[i - 1][a];
jmp[i][j] = {x, min(b, c + y), c + z};
}
}
// for (ll i = 1; i <= n; ++i) {
// cout << jmp[0][i].second << ' ';
// }
// cout << '\n';
for (ll i = 0; i < q; ++i) {
ll idx, r;
cin >> idx >> r;
auto& [a, b] = edges[idx - 1];
// a is deeper
if (depth[b] > depth[a]) swap(a, b);
if (tin[r] <= tout[a] && tin[r] >= tin[a]) {
ll ans = shop_in_subtree[r];
ll sum = 0;
for (ll j = 19; j >= 0; --j) {
auto& [x, y, z] = jmp[j][r];
if (x != 0 && depth[x] >= depth[a]) {
ans = min(ans, y + sum);
r = x;
sum += z;
}
}
ans = min(ans, shop_in_subtree[r] + sum);
if (ans == INF) {
cout << "oo\n";
} else {
cout << ans << '\n';
}
} else {
cout << "escaped\n";
}
}
}
Compilation message
valley.cpp: In function 'void dfs(ll, ll, ll)':
valley.cpp:24:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
24 | for (auto& [x, w] : adj[n]) {
| ^
valley.cpp: In function 'int main()':
valley.cpp:53:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
53 | auto& [a, b, c] = jmp[i - 1][j];
| ^
valley.cpp:54:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | auto& [x, y, z] = jmp[i - 1][a];
| ^
valley.cpp:67:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
67 | auto& [a, b] = edges[idx - 1];
| ^
valley.cpp:74:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
74 | auto& [x, y, z] = jmp[j][r];
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
44636 KB |
Output is correct |
2 |
Correct |
22 ms |
44740 KB |
Output is correct |
3 |
Correct |
22 ms |
44632 KB |
Output is correct |
4 |
Correct |
23 ms |
44632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
44636 KB |
Output is correct |
2 |
Correct |
22 ms |
44740 KB |
Output is correct |
3 |
Correct |
22 ms |
44632 KB |
Output is correct |
4 |
Correct |
23 ms |
44632 KB |
Output is correct |
5 |
Correct |
11 ms |
44636 KB |
Output is correct |
6 |
Correct |
10 ms |
44664 KB |
Output is correct |
7 |
Correct |
10 ms |
44644 KB |
Output is correct |
8 |
Correct |
10 ms |
44636 KB |
Output is correct |
9 |
Correct |
11 ms |
44636 KB |
Output is correct |
10 |
Correct |
11 ms |
45036 KB |
Output is correct |
11 |
Correct |
10 ms |
44636 KB |
Output is correct |
12 |
Correct |
10 ms |
44632 KB |
Output is correct |
13 |
Correct |
12 ms |
44636 KB |
Output is correct |
14 |
Correct |
10 ms |
44636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
331 ms |
64052 KB |
Output is correct |
2 |
Correct |
333 ms |
64084 KB |
Output is correct |
3 |
Correct |
334 ms |
64184 KB |
Output is correct |
4 |
Correct |
348 ms |
65996 KB |
Output is correct |
5 |
Correct |
307 ms |
66116 KB |
Output is correct |
6 |
Correct |
345 ms |
68280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
44636 KB |
Output is correct |
2 |
Correct |
22 ms |
44740 KB |
Output is correct |
3 |
Correct |
22 ms |
44632 KB |
Output is correct |
4 |
Correct |
23 ms |
44632 KB |
Output is correct |
5 |
Correct |
11 ms |
44636 KB |
Output is correct |
6 |
Correct |
10 ms |
44664 KB |
Output is correct |
7 |
Correct |
10 ms |
44644 KB |
Output is correct |
8 |
Correct |
10 ms |
44636 KB |
Output is correct |
9 |
Correct |
11 ms |
44636 KB |
Output is correct |
10 |
Correct |
11 ms |
45036 KB |
Output is correct |
11 |
Correct |
10 ms |
44636 KB |
Output is correct |
12 |
Correct |
10 ms |
44632 KB |
Output is correct |
13 |
Correct |
12 ms |
44636 KB |
Output is correct |
14 |
Correct |
10 ms |
44636 KB |
Output is correct |
15 |
Correct |
331 ms |
64052 KB |
Output is correct |
16 |
Correct |
333 ms |
64084 KB |
Output is correct |
17 |
Correct |
334 ms |
64184 KB |
Output is correct |
18 |
Correct |
348 ms |
65996 KB |
Output is correct |
19 |
Correct |
307 ms |
66116 KB |
Output is correct |
20 |
Correct |
345 ms |
68280 KB |
Output is correct |
21 |
Correct |
326 ms |
63572 KB |
Output is correct |
22 |
Correct |
331 ms |
63388 KB |
Output is correct |
23 |
Correct |
294 ms |
63528 KB |
Output is correct |
24 |
Correct |
340 ms |
65548 KB |
Output is correct |
25 |
Correct |
328 ms |
68580 KB |
Output is correct |
26 |
Correct |
305 ms |
63640 KB |
Output is correct |
27 |
Correct |
294 ms |
63496 KB |
Output is correct |
28 |
Correct |
313 ms |
63828 KB |
Output is correct |
29 |
Correct |
322 ms |
65308 KB |
Output is correct |
30 |
Correct |
357 ms |
66680 KB |
Output is correct |
31 |
Correct |
287 ms |
63740 KB |
Output is correct |
32 |
Correct |
304 ms |
63608 KB |
Output is correct |
33 |
Correct |
343 ms |
63764 KB |
Output is correct |
34 |
Correct |
345 ms |
65612 KB |
Output is correct |
35 |
Correct |
314 ms |
68660 KB |
Output is correct |
36 |
Correct |
298 ms |
65764 KB |
Output is correct |