# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
547578 |
2022-04-11T02:56:11 Z |
Jomnoi |
Valley (BOI19_valley) |
C++17 |
|
337 ms |
29688 KB |
#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;
const int MAX_N = 1e5 + 10;
const long long INF = 1e18 + 7;
int A[MAX_N], B[MAX_N], W[MAX_N];
vector <pair <int, int>> graph[MAX_N];
long long dist[MAX_N];
// Heavy Light Decomposition
int timer;
int sz[MAX_N], depth[MAX_N], parent[MAX_N][20];
int head[MAX_N], st[MAX_N], pos[MAX_N];
// Segment Tree
long long tree[4 * MAX_N];
int get_size(const int &u, const int &p) {
sz[u] = 1;
for(int i = 1; i < 20; i++) {
parent[u][i] = parent[parent[u][i - 1]][i - 1];
}
for(auto [v, w] : graph[u]) {
if(v == p) {
continue;
}
depth[v] = depth[u] + 1;
parent[v][0] = u;
dist[v] = dist[u] + w;
sz[u] += get_size(v, u);
}
return sz[u];
}
void build_hld(const int &u, const int &p, const int &t) {
timer++;
head[u] = t;
st[u] = timer;
pos[timer] = u;
int max_size = 0, biggest = -1;
for(auto [v, w] : graph[u]) {
if(v != p and max_size < sz[v]) {
max_size = sz[v];
biggest = v;
}
}
if(biggest != -1) {
build_hld(biggest, u, t);
}
for(auto [v, w] : graph[u]) {
if(v != p and v != biggest) {
build_hld(v, u, v);
}
}
}
int find_lca(const int &a, const int &b) {
int u = a, v = b;
if(depth[u] < depth[v]) {
swap(u, v);
}
for(int i = 19; i >= 0; i--) {
if(depth[parent[u][i]] >= depth[v]) {
u = parent[u][i];
}
}
for(int i = 19; i >= 0; i--) {
if(parent[u][i] != parent[v][i]) {
u = parent[u][i];
v = parent[v][i];
}
}
return (u == v ? u : parent[u][0]);
}
void build_seg(const int &idx, const int &l, const int &r) {
tree[idx] = INF;
if(l == r) {
return;
}
int mid = (l + r) / 2;
build_seg(idx * 2, l, mid);
build_seg(idx * 2 + 1, mid + 1, r);
}
void update(const int &idx, const int &l, const int &r, const int &ql, const int &qr, const long long &v) {
if(r < ql or qr < l) {
return;
}
if(ql <= l and r <= qr) {
tree[idx] = min(tree[idx], v);
return;
}
int mid = (l + r) / 2;
update(idx * 2, l, mid, ql, qr, v);
update(idx * 2 + 1, mid + 1, r, ql, qr, v);
}
void construct(const int &idx, const int &l, const int &r) {
if(l == r) {
if(tree[idx] != INF) {
tree[idx] -= 2 * dist[pos[l]];
}
return;
}
tree[idx * 2] = min(tree[idx * 2], tree[idx]);
tree[idx * 2 + 1] = min(tree[idx * 2 + 1], tree[idx]);
int mid = (l + r) / 2;
construct(idx * 2, l, mid);
construct(idx * 2 + 1, mid + 1, r);
tree[idx] = min(tree[idx * 2], tree[idx * 2 + 1]);
}
long long query(int idx, int l, int r, int ql, int qr) {
if(r < ql or qr < l) {
return INF;
}
if(ql <= l and r <= qr) {
return tree[idx];
}
int mid = (l + r) / 2;
return min(query(idx * 2, l, mid, ql, qr), query(idx * 2 + 1, mid + 1, r, ql, qr));
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, S, Q, E;
cin >> N >> S >> Q >> E;
for(int i = 1; i <= N - 1; i++) {
cin >> A[i] >> B[i] >> W[i];
graph[A[i]].emplace_back(B[i], W[i]);
graph[B[i]].emplace_back(A[i], W[i]);
}
depth[0] = -1;
get_size(E, -1);
build_hld(E, -1, E);
build_seg(1, 1, N);
for(int i = 1; i <= S; i++) {
int C;
cin >> C;
int u = C;
while(true) {
if(head[E] == head[u]) {
update(1, 1, N, st[E], st[u], dist[C]);
break;
}
update(1, 1, N, st[head[u]], st[u], dist[C]);
u = parent[head[u]][0];
}
}
construct(1, 1, N);
for(int i = 1; i <= N - 1; i++) {
if(depth[A[i]] > depth[B[i]]) {
swap(A[i], B[i]);
}
}
for(int i = 1; i <= Q; i++) {
int I, R;
cin >> I >> R;
int lca = find_lca(B[I], R);
if(lca != B[I]) {
cout << "escaped\n";
continue;
}
int u = R;
long long res = INF;
while(true) {
if(head[lca] == head[u]) {
res = min(res, query(1, 1, N, st[lca], st[u]));
break;
}
res = min(res, query(1, 1, N, st[head[u]], st[u]));
u = parent[head[u]][0];
}
if(res != INF) {
cout << res + dist[R] << '\n';
}
else {
cout << "oo\n";
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2820 KB |
Output is correct |
2 |
Correct |
6 ms |
2824 KB |
Output is correct |
3 |
Correct |
6 ms |
2828 KB |
Output is correct |
4 |
Correct |
6 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2820 KB |
Output is correct |
2 |
Correct |
6 ms |
2824 KB |
Output is correct |
3 |
Correct |
6 ms |
2828 KB |
Output is correct |
4 |
Correct |
6 ms |
2772 KB |
Output is correct |
5 |
Correct |
3 ms |
2824 KB |
Output is correct |
6 |
Correct |
3 ms |
2900 KB |
Output is correct |
7 |
Correct |
3 ms |
2952 KB |
Output is correct |
8 |
Correct |
3 ms |
2900 KB |
Output is correct |
9 |
Correct |
3 ms |
2900 KB |
Output is correct |
10 |
Correct |
3 ms |
2900 KB |
Output is correct |
11 |
Correct |
3 ms |
2832 KB |
Output is correct |
12 |
Correct |
4 ms |
2900 KB |
Output is correct |
13 |
Correct |
3 ms |
2900 KB |
Output is correct |
14 |
Correct |
4 ms |
2852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
277 ms |
20932 KB |
Output is correct |
2 |
Correct |
337 ms |
24532 KB |
Output is correct |
3 |
Correct |
333 ms |
24580 KB |
Output is correct |
4 |
Correct |
320 ms |
26596 KB |
Output is correct |
5 |
Correct |
309 ms |
26660 KB |
Output is correct |
6 |
Correct |
301 ms |
28964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2820 KB |
Output is correct |
2 |
Correct |
6 ms |
2824 KB |
Output is correct |
3 |
Correct |
6 ms |
2828 KB |
Output is correct |
4 |
Correct |
6 ms |
2772 KB |
Output is correct |
5 |
Correct |
3 ms |
2824 KB |
Output is correct |
6 |
Correct |
3 ms |
2900 KB |
Output is correct |
7 |
Correct |
3 ms |
2952 KB |
Output is correct |
8 |
Correct |
3 ms |
2900 KB |
Output is correct |
9 |
Correct |
3 ms |
2900 KB |
Output is correct |
10 |
Correct |
3 ms |
2900 KB |
Output is correct |
11 |
Correct |
3 ms |
2832 KB |
Output is correct |
12 |
Correct |
4 ms |
2900 KB |
Output is correct |
13 |
Correct |
3 ms |
2900 KB |
Output is correct |
14 |
Correct |
4 ms |
2852 KB |
Output is correct |
15 |
Correct |
277 ms |
20932 KB |
Output is correct |
16 |
Correct |
337 ms |
24532 KB |
Output is correct |
17 |
Correct |
333 ms |
24580 KB |
Output is correct |
18 |
Correct |
320 ms |
26596 KB |
Output is correct |
19 |
Correct |
309 ms |
26660 KB |
Output is correct |
20 |
Correct |
301 ms |
28964 KB |
Output is correct |
21 |
Correct |
159 ms |
24376 KB |
Output is correct |
22 |
Correct |
172 ms |
24012 KB |
Output is correct |
23 |
Correct |
192 ms |
24012 KB |
Output is correct |
24 |
Correct |
225 ms |
26572 KB |
Output is correct |
25 |
Correct |
224 ms |
29688 KB |
Output is correct |
26 |
Correct |
161 ms |
24244 KB |
Output is correct |
27 |
Correct |
172 ms |
23936 KB |
Output is correct |
28 |
Correct |
195 ms |
24016 KB |
Output is correct |
29 |
Correct |
234 ms |
25508 KB |
Output is correct |
30 |
Correct |
247 ms |
27192 KB |
Output is correct |
31 |
Correct |
181 ms |
24352 KB |
Output is correct |
32 |
Correct |
214 ms |
24112 KB |
Output is correct |
33 |
Correct |
207 ms |
24044 KB |
Output is correct |
34 |
Correct |
254 ms |
26304 KB |
Output is correct |
35 |
Correct |
230 ms |
29644 KB |
Output is correct |
36 |
Correct |
281 ms |
26348 KB |
Output is correct |