# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
879975 |
2023-11-28T12:35:19 Z |
VectorLi |
Valley (BOI19_valley) |
C++17 |
|
106 ms |
40520 KB |
#include <bits/stdc++.h>
#define long long long
using namespace std;
const int V = (int) 1E5, K = 17;
const long MAX = numeric_limits<long>::max();
struct Element {
long a;
};
const Element E = {MAX};
Element operator + (Element u, Element v) {
Element w;
w.a = min(u.a, v.a);
return w;
}
int n, m, q, s;
vector<pair<int, long>> e1[V];
pair<int, int> e2[V - 1];
bool t[V];
int p[K][V], d1[V], h[V], l[V], c;
long d2[V], f[V];
Element g[K][V];
void DFS(int u) {
h[u] = 1;
l[u] = c;
c = c + 1;
f[u] = t[u] ? d2[u] : MAX;
for (auto [v, w] : e1[u]) {
if (v != p[0][u]) {
p[0][v] = u;
d1[v] = d1[u] + 1;
d2[v] = d2[u] + w;
DFS(v);
h[u] = h[u] + h[v];
f[u] = min(f[u], f[v]);
}
}
}
Element query(int u, int v) {
Element x = E;
if (d1[u] > d1[v]) {
swap(u, v);
}
for (int i = K - 1; i >= 0; i--) {
if ((d1[v] - d1[u]) >> i & 1) {
x = x + g[i][v];
v = p[i][v];
}
}
if (u == v) {
return x + g[0][u];
}
assert(false);
}
int lower(int i) {
int u, v;
tie(u, v) = e2[i];
return d1[u] > d1[v] ? u : v;
}
void solve() {
cin >> n >> m >> q >> s;
s = s - 1;
for (int i = 0; i < n - 1; i++) {
int u, v;
long w;
cin >> u >> v >> w;
u = u - 1, v = v - 1;
e1[u].push_back({v, w});
e1[v].push_back({u, w});
e2[i] = {u, v};
}
for (int i = 0; i < m; i++) {
int u;
cin >> u;
u = u - 1;
t[u] = true;
}
p[0][s] = -1;
DFS(s);
for (int u = 0; u < n; u++) {
if (f[u] < MAX) {
f[u] = f[u] - d2[u] * 2;
}
g[0][u] = {f[u]};
}
for (int i = 0; i < K - 1; i++) {
for (int u = 0; u < n; u++) {
if (p[i][u] < 0) {
p[i + 1][u] = -1;
g[i + 1][u] = g[i][u];
} else {
p[i + 1][u] = p[i][p[i][u]];
g[i + 1][u] = g[i][u] + g[i][p[i][u]];
}
}
}
for (int i = 0; i < q; i++) {
int j;
cin >> j;
j = j - 1;
int u, v;
cin >> u;
u = u - 1;
v = lower(j);
if (not (l[v] <= l[u] && l[v] + h[v] > l[u])) {
cout << "escaped" << "\n";
} else {
Element x = query(u, v);
if (x.a < MAX) {
cout << d2[u] + x.a << "\n";
} else {
cout << "oo" << "\n";
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
26204 KB |
Output is correct |
2 |
Correct |
5 ms |
26204 KB |
Output is correct |
3 |
Correct |
6 ms |
26204 KB |
Output is correct |
4 |
Correct |
5 ms |
24156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
26204 KB |
Output is correct |
2 |
Correct |
5 ms |
26204 KB |
Output is correct |
3 |
Correct |
6 ms |
26204 KB |
Output is correct |
4 |
Correct |
5 ms |
24156 KB |
Output is correct |
5 |
Correct |
4 ms |
26204 KB |
Output is correct |
6 |
Correct |
5 ms |
26200 KB |
Output is correct |
7 |
Correct |
4 ms |
26204 KB |
Output is correct |
8 |
Correct |
5 ms |
26204 KB |
Output is correct |
9 |
Correct |
4 ms |
24156 KB |
Output is correct |
10 |
Correct |
4 ms |
26256 KB |
Output is correct |
11 |
Correct |
4 ms |
24156 KB |
Output is correct |
12 |
Correct |
5 ms |
24256 KB |
Output is correct |
13 |
Correct |
4 ms |
24156 KB |
Output is correct |
14 |
Correct |
4 ms |
26200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
35824 KB |
Output is correct |
2 |
Correct |
102 ms |
35624 KB |
Output is correct |
3 |
Correct |
85 ms |
35928 KB |
Output is correct |
4 |
Correct |
93 ms |
37944 KB |
Output is correct |
5 |
Correct |
80 ms |
37972 KB |
Output is correct |
6 |
Correct |
106 ms |
40244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
26204 KB |
Output is correct |
2 |
Correct |
5 ms |
26204 KB |
Output is correct |
3 |
Correct |
6 ms |
26204 KB |
Output is correct |
4 |
Correct |
5 ms |
24156 KB |
Output is correct |
5 |
Correct |
4 ms |
26204 KB |
Output is correct |
6 |
Correct |
5 ms |
26200 KB |
Output is correct |
7 |
Correct |
4 ms |
26204 KB |
Output is correct |
8 |
Correct |
5 ms |
26204 KB |
Output is correct |
9 |
Correct |
4 ms |
24156 KB |
Output is correct |
10 |
Correct |
4 ms |
26256 KB |
Output is correct |
11 |
Correct |
4 ms |
24156 KB |
Output is correct |
12 |
Correct |
5 ms |
24256 KB |
Output is correct |
13 |
Correct |
4 ms |
24156 KB |
Output is correct |
14 |
Correct |
4 ms |
26200 KB |
Output is correct |
15 |
Correct |
72 ms |
35824 KB |
Output is correct |
16 |
Correct |
102 ms |
35624 KB |
Output is correct |
17 |
Correct |
85 ms |
35928 KB |
Output is correct |
18 |
Correct |
93 ms |
37944 KB |
Output is correct |
19 |
Correct |
80 ms |
37972 KB |
Output is correct |
20 |
Correct |
106 ms |
40244 KB |
Output is correct |
21 |
Correct |
68 ms |
35304 KB |
Output is correct |
22 |
Correct |
68 ms |
35152 KB |
Output is correct |
23 |
Correct |
81 ms |
35300 KB |
Output is correct |
24 |
Correct |
98 ms |
37428 KB |
Output is correct |
25 |
Correct |
86 ms |
40388 KB |
Output is correct |
26 |
Correct |
64 ms |
35492 KB |
Output is correct |
27 |
Correct |
74 ms |
35156 KB |
Output is correct |
28 |
Correct |
74 ms |
35540 KB |
Output is correct |
29 |
Correct |
81 ms |
36944 KB |
Output is correct |
30 |
Correct |
88 ms |
38460 KB |
Output is correct |
31 |
Correct |
68 ms |
35408 KB |
Output is correct |
32 |
Correct |
69 ms |
35228 KB |
Output is correct |
33 |
Correct |
77 ms |
35664 KB |
Output is correct |
34 |
Correct |
89 ms |
37428 KB |
Output is correct |
35 |
Correct |
88 ms |
40520 KB |
Output is correct |
36 |
Correct |
81 ms |
37480 KB |
Output is correct |