# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
467580 |
2021-08-23T18:11:26 Z |
Rico64 |
Valley (BOI19_valley) |
C++14 |
|
639 ms |
38060 KB |
#include <iostream>
#include <vector>
#include <queue>
const long long INT63_MAX = INT64_MAX / 2;
const int MAX_N = 100000;
const int MAX_LOGN = 17;
struct edge {
int v, c;
};
using namespace std;
int n, sl, ql, root;
vector<edge> graph[MAX_N];
int ec[MAX_N];
int parent[MAX_N][MAX_LOGN], depth[MAX_N];
long long cost[MAX_N], shopcost[MAX_N];
long long scost[MAX_N][MAX_LOGN];
void search1(int v, int p, long long cc) {
cost[v] = cc;
parent[v][0] = p;
for (int i = 1; i < MAX_LOGN; ++i) {
parent[v][i] = (p < 0) ? (-1) : (p = parent[p][i-1]);
}
for (const edge& e : graph[v]) {
if (e.v == parent[v][0]) continue;
depth[e.v] = depth[v] + 1;
search1(e.v, v, cc + (long long)e.c);
shopcost[v] = min(shopcost[v], shopcost[e.v] + (long long)e.c);
}
}
void search2(int v) {
scost[v][0] = shopcost[v];
for (int i = 1; i < MAX_LOGN; ++i) {
int p = parent[v][i-1];
scost[v][i] = (p < 0) ? (-1) : (min(scost[v][i-1], scost[p][i-1] + cost[v] - cost[p]));
}
for (const edge& e : graph[v]) {
if (e.v == parent[v][0]) continue;
search2(e.v);
}
}
int main() {
cin >> n >> sl >> ql >> root;
root--;
int xs[n-1], ys[n-1];
for (int i = 0, f, t, c; i < n-1; ++i) {
cin >> f >> t >> c;
f--; t--;
xs[i] = f;
ys[i] = t;
graph[f].push_back({t, c});
graph[t].push_back({f, c});
}
fill(shopcost, shopcost + n, INT63_MAX);
for (int i = 0, s; i < sl; ++i) {
cin >> s;
s--;
shopcost[s] = 0;
}
depth[root] = 0;
search1(root, -1, 0);
// for (int v = 0; v < n; ++v) {
// for (int i = 0; i < MAX_LOGN; ++i) cout << parent[v][i] << ' ';
// cout << endl;
// }
for (int i = 0; i < n-1; ++i) {
ec[i] = (parent[xs[i]][0] == ys[i]) ? (xs[i]) : (ys[i]);
}
// for (int i = 0; i < n-1; ++i) cout << ec[i] << ' '; cout << endl;
// for (int i = 0; i < n; ++i) cout << depth[i] << ' '; cout << endl;
// for (int i = 0; i < n; ++i) cout << cost[i] << ' '; cout << endl;
search2(root);
// for (int v = 0; v < n; ++v) {
// cout << v << " : ";
// for (int i = 0; i < MAX_LOGN; ++i) cout << scost[v][i] << ' ';
// cout << endl;
// }
;
for (int it = 0, i, r; it < ql; ++it) {
cin >> i >> r;
i--; r--;
int c = ec[i];
int cr = r;
long long res = INT63_MAX;
for (int d = depth[r] - depth[c]; d > 0; d ^= d & -d) {
res = min(res, scost[cr][__builtin_ctz(d)] + cost[r] - cost[cr]);
cr = parent[cr][__builtin_ctz(d)];
}
if (cr != c) {
cout << "escaped" << endl;
continue;
}
res = min(res, scost[c][0] + cost[r] - cost[c]);
if (res == INT63_MAX) {
cout << "oo" << endl;
} else {
cout << res << endl;
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
2764 KB |
Output is correct |
2 |
Correct |
23 ms |
2840 KB |
Output is correct |
3 |
Correct |
22 ms |
2792 KB |
Output is correct |
4 |
Correct |
27 ms |
2832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
2764 KB |
Output is correct |
2 |
Correct |
23 ms |
2840 KB |
Output is correct |
3 |
Correct |
22 ms |
2792 KB |
Output is correct |
4 |
Correct |
27 ms |
2832 KB |
Output is correct |
5 |
Correct |
5 ms |
2892 KB |
Output is correct |
6 |
Correct |
5 ms |
2892 KB |
Output is correct |
7 |
Correct |
5 ms |
2892 KB |
Output is correct |
8 |
Correct |
5 ms |
2892 KB |
Output is correct |
9 |
Correct |
5 ms |
2916 KB |
Output is correct |
10 |
Correct |
5 ms |
2920 KB |
Output is correct |
11 |
Correct |
5 ms |
2892 KB |
Output is correct |
12 |
Correct |
5 ms |
2892 KB |
Output is correct |
13 |
Correct |
6 ms |
2892 KB |
Output is correct |
14 |
Correct |
5 ms |
2892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
473 ms |
34112 KB |
Output is correct |
2 |
Correct |
488 ms |
33904 KB |
Output is correct |
3 |
Correct |
507 ms |
33932 KB |
Output is correct |
4 |
Correct |
523 ms |
35516 KB |
Output is correct |
5 |
Correct |
545 ms |
35624 KB |
Output is correct |
6 |
Correct |
553 ms |
37444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
2764 KB |
Output is correct |
2 |
Correct |
23 ms |
2840 KB |
Output is correct |
3 |
Correct |
22 ms |
2792 KB |
Output is correct |
4 |
Correct |
27 ms |
2832 KB |
Output is correct |
5 |
Correct |
5 ms |
2892 KB |
Output is correct |
6 |
Correct |
5 ms |
2892 KB |
Output is correct |
7 |
Correct |
5 ms |
2892 KB |
Output is correct |
8 |
Correct |
5 ms |
2892 KB |
Output is correct |
9 |
Correct |
5 ms |
2916 KB |
Output is correct |
10 |
Correct |
5 ms |
2920 KB |
Output is correct |
11 |
Correct |
5 ms |
2892 KB |
Output is correct |
12 |
Correct |
5 ms |
2892 KB |
Output is correct |
13 |
Correct |
6 ms |
2892 KB |
Output is correct |
14 |
Correct |
5 ms |
2892 KB |
Output is correct |
15 |
Correct |
473 ms |
34112 KB |
Output is correct |
16 |
Correct |
488 ms |
33904 KB |
Output is correct |
17 |
Correct |
507 ms |
33932 KB |
Output is correct |
18 |
Correct |
523 ms |
35516 KB |
Output is correct |
19 |
Correct |
545 ms |
35624 KB |
Output is correct |
20 |
Correct |
553 ms |
37444 KB |
Output is correct |
21 |
Correct |
430 ms |
33496 KB |
Output is correct |
22 |
Correct |
491 ms |
33212 KB |
Output is correct |
23 |
Correct |
456 ms |
33132 KB |
Output is correct |
24 |
Correct |
540 ms |
35188 KB |
Output is correct |
25 |
Correct |
636 ms |
38060 KB |
Output is correct |
26 |
Correct |
435 ms |
33564 KB |
Output is correct |
27 |
Correct |
450 ms |
33252 KB |
Output is correct |
28 |
Correct |
478 ms |
33188 KB |
Output is correct |
29 |
Correct |
539 ms |
34536 KB |
Output is correct |
30 |
Correct |
639 ms |
35920 KB |
Output is correct |
31 |
Correct |
458 ms |
33600 KB |
Output is correct |
32 |
Correct |
482 ms |
33344 KB |
Output is correct |
33 |
Correct |
557 ms |
33364 KB |
Output is correct |
34 |
Correct |
560 ms |
35080 KB |
Output is correct |
35 |
Correct |
615 ms |
38060 KB |
Output is correct |
36 |
Correct |
518 ms |
35308 KB |
Output is correct |