# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
544698 |
2022-04-02T14:56:42 Z |
valerikk |
Valley (BOI19_valley) |
C++17 |
|
217 ms |
44300 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100100;
const int K = 20;
const ll INF = 1e18;
int n, s, q, e;
int a[N], b[N];
vector<pair<ll, int>> g[N];
int c[N];
bool good[N];
int tin[N], tout[N], tt;
ll h[N];
ll d[N];
int up[K][N];
ll mn[K][N];
ll val[N];
bool anc(int v, int u) {
return tin[v] <= tin[u] && tout[v] >= tout[u];
}
void dfs(int v) {
tin[v] = tt++;
d[v] = INF;
for (auto [w, u] : g[v]) {
if (u != up[0][v]) {
up[0][u] = v;
h[u] = h[v] + w;
dfs(u);
d[v] = min(d[v], d[u] + w);
}
}
if (good[v]) {
d[v] = 0;
}
val[v] = d[v] - h[v];
tout[v] = tt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> s >> q >> e;
--e;
for (int i = 0; i < n - 1; ++i) {
ll w;
cin >> a[i] >> b[i] >> w;
--a[i];
--b[i];
g[a[i]].emplace_back(w, b[i]);
g[b[i]].emplace_back(w, a[i]);
}
for (int i = 0; i < s; ++i) {
cin >> c[i];
--c[i];
good[c[i]] = true;
}
up[0][e] = e;
dfs(e);
for (int i = 0; i < n - 1; ++i) {
if (tin[a[i]] > tin[b[i]]) {
swap(a[i], b[i]);
}
}
for (int v = 0; v < n; ++v) {
mn[0][v] = val[up[0][v]];
}
for (int i = 1; i < K; ++i) {
for (int v = 0; v < n; ++v) {
up[i][v] = up[i - 1][up[i - 1][v]];
mn[i][v] = min(mn[i - 1][v], mn[i - 1][up[i - 1][v]]);
}
}
while (q--) {
int id, v;
cin >> id >> v;
--id;
--v;
if (!anc(b[id], v)) {
cout << "escaped\n";
continue;
}
if (d[b[id]] == INF) {
cout << "oo\n";
continue;
}
int vv = v;
ll ans = val[v];
for (int i = K - 1; i >= 0; --i) {
if (anc(b[id], up[i][v])) {
ans = min(ans, mn[i][v]);
v = up[i][v];
}
}
ans += h[vv];
cout << ans << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3080 KB |
Output is correct |
2 |
Correct |
6 ms |
3028 KB |
Output is correct |
3 |
Correct |
5 ms |
3084 KB |
Output is correct |
4 |
Correct |
4 ms |
3028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3080 KB |
Output is correct |
2 |
Correct |
6 ms |
3028 KB |
Output is correct |
3 |
Correct |
5 ms |
3084 KB |
Output is correct |
4 |
Correct |
4 ms |
3028 KB |
Output is correct |
5 |
Correct |
3 ms |
3212 KB |
Output is correct |
6 |
Correct |
4 ms |
3284 KB |
Output is correct |
7 |
Correct |
2 ms |
3284 KB |
Output is correct |
8 |
Correct |
2 ms |
3284 KB |
Output is correct |
9 |
Correct |
2 ms |
3284 KB |
Output is correct |
10 |
Correct |
3 ms |
3284 KB |
Output is correct |
11 |
Correct |
3 ms |
3264 KB |
Output is correct |
12 |
Correct |
3 ms |
3284 KB |
Output is correct |
13 |
Correct |
3 ms |
3284 KB |
Output is correct |
14 |
Correct |
3 ms |
3284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
150 ms |
40164 KB |
Output is correct |
2 |
Correct |
127 ms |
39928 KB |
Output is correct |
3 |
Correct |
146 ms |
40148 KB |
Output is correct |
4 |
Correct |
217 ms |
42032 KB |
Output is correct |
5 |
Correct |
136 ms |
42144 KB |
Output is correct |
6 |
Correct |
194 ms |
44284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3080 KB |
Output is correct |
2 |
Correct |
6 ms |
3028 KB |
Output is correct |
3 |
Correct |
5 ms |
3084 KB |
Output is correct |
4 |
Correct |
4 ms |
3028 KB |
Output is correct |
5 |
Correct |
3 ms |
3212 KB |
Output is correct |
6 |
Correct |
4 ms |
3284 KB |
Output is correct |
7 |
Correct |
2 ms |
3284 KB |
Output is correct |
8 |
Correct |
2 ms |
3284 KB |
Output is correct |
9 |
Correct |
2 ms |
3284 KB |
Output is correct |
10 |
Correct |
3 ms |
3284 KB |
Output is correct |
11 |
Correct |
3 ms |
3264 KB |
Output is correct |
12 |
Correct |
3 ms |
3284 KB |
Output is correct |
13 |
Correct |
3 ms |
3284 KB |
Output is correct |
14 |
Correct |
3 ms |
3284 KB |
Output is correct |
15 |
Correct |
150 ms |
40164 KB |
Output is correct |
16 |
Correct |
127 ms |
39928 KB |
Output is correct |
17 |
Correct |
146 ms |
40148 KB |
Output is correct |
18 |
Correct |
217 ms |
42032 KB |
Output is correct |
19 |
Correct |
136 ms |
42144 KB |
Output is correct |
20 |
Correct |
194 ms |
44284 KB |
Output is correct |
21 |
Correct |
107 ms |
39176 KB |
Output is correct |
22 |
Correct |
106 ms |
38988 KB |
Output is correct |
23 |
Correct |
125 ms |
39220 KB |
Output is correct |
24 |
Correct |
119 ms |
41328 KB |
Output is correct |
25 |
Correct |
154 ms |
44300 KB |
Output is correct |
26 |
Correct |
101 ms |
39260 KB |
Output is correct |
27 |
Correct |
106 ms |
39084 KB |
Output is correct |
28 |
Correct |
123 ms |
39336 KB |
Output is correct |
29 |
Correct |
137 ms |
40780 KB |
Output is correct |
30 |
Correct |
171 ms |
42428 KB |
Output is correct |
31 |
Correct |
139 ms |
39356 KB |
Output is correct |
32 |
Correct |
116 ms |
39180 KB |
Output is correct |
33 |
Correct |
124 ms |
39444 KB |
Output is correct |
34 |
Correct |
172 ms |
41504 KB |
Output is correct |
35 |
Correct |
150 ms |
44252 KB |
Output is correct |
36 |
Correct |
133 ms |
41424 KB |
Output is correct |