#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, s, q, e, h[N], par[20][N], st[N], en[N], in[N], Time = 0;
long long d[N], ans[N];
vector <pair <int, int> > g[N];
pair <int, pair <int, int> > edge[N];
bool marked[N];
vector <pair <int, int> > queries[N];
struct SegmentTree {
long long node[N << 2], lz[N << 2];
void init (int i, int l, int r) {
if (l == r) {
node[i] = (marked[in[l]] ? d[in[l]] : (long long)1e18);
lz[i] = 0;
return;
}
int mid = l + r >> 1;
init(i << 1, l, mid);
init(i << 1 | 1, mid + 1, r);
node[i] = min(node[i << 1], node[i << 1 | 1]);
lz[i] = 0;
}
void propagate (int i, int l, int r) {
if (lz[i]) {
node[i] += lz[i];
if (l != r) {
lz[i << 1] += lz[i];
lz[i << 1 | 1] += lz[i];
}
lz[i] = 0;
}
}
void update (int i, int l, int r, int a, int b, int val) {
propagate(i, l, r);
if (l > r || a > r || b < l) return;
if (a <= l && r <= b) {
node[i] += val;
if (l != r) {
lz[i << 1] += val;
lz[i << 1 | 1] += val;
}
return;
}
int mid = l + r >> 1;
update(i << 1, l, mid, a, b, val);
update(i << 1 | 1, mid + 1, r, a, b, val);
node[i] = min(node[i << 1], node[i << 1 | 1]);
}
long long query (int i, int l, int r, int a, int b) {
if (l > r || a > r || b < l) return (long long)1e18;
propagate(i, l, r);
if (a <= l && r <= b) return node[i];
int mid = l + r >> 1;
return min(query(i << 1, l, mid, a, b), query(i << 1 | 1, mid + 1, r, a, b));
}
} it;
void dfs (int u, int p) {
st[u] = ++Time;
in[Time] = u;
for (auto ii: g[u]) {
int w = ii.first, v = ii.second;
if (v == p) continue;
h[v] = h[u] + 1;
d[v] = d[u] + w;
par[0][v] = u;
dfs(v, u);
}
en[u] = Time;
}
void makeLCA(){
for (int i = 1; i < 20; i++) {
for (int j = 1; j <= n; j++) {
if (par[i - 1][j] != -1) par[i][j] = par[i - 1][par[i - 1][j]];
}
}
}
int LCA (int x, int y) {
if (h[x] > h[y]) swap(x, y);
for (int i = 19; i >= 0; i--) {
if (par[i][y] != -1 && h[y] - (1 << i) >= h[x]) {
y = par[i][y];
}
}
if (x == y) return x;
for (int i = 19; i >= 0; i--) {
if (par[i][x] != -1 && par[i][y] != -1 && par[i][x] != par[i][y]) {
x = par[i][x];
y = par[i][y];
}
}
if (x == y) return x;
return par[0][x];
}
long long dist (int u, int v) {
return d[u] + d[v] - 2 * d[LCA(u, v)];
}
void solve (int ver, int p) {
for (auto ii: queries[ver]) {
int road_id = ii.first, id = ii.second;
int w = edge[road_id].first, u = edge[road_id].second.first, v = edge[road_id].second.second;
if (dist(e, v) + dist(u, ver) + w == dist(ver, e)) {
ans[id] = it.query(1, 1, n, st[u], en[u]);
}
else if (dist(e, u) + dist(v, ver) + w == dist(ver, e)) {
ans[id] = it.query(1, 1, n, st[v], en[v]);
}
else {
ans[id] = -1;
}
}
for (auto ii: g[ver]) {
int w = ii.first, v = ii.second;
if (v == p) continue;
it.update(1, 1, n, st[v], en[v], -w);
it.update(1, 1, n, 1, st[v] - 1, w);
it.update(1, 1, n, en[v] + 1, n, w);
solve(v, ver);
it.update(1, 1, n, st[v], en[v], w);
it.update(1, 1, n, 1, st[v] - 1, -w);
it.update(1, 1, n, en[v] + 1, n, -w);
}
}
int main(){
scanf("%d %d %d %d", &n, &s, &q, &e); memset(par, -1, sizeof(par));
for (int i = 1; i <= n - 1; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
g[u].push_back({w, v});
g[v].push_back({w, u});
edge[i] = {w, {u, v}};
}
for (int i = 1; i <= s; i++) {
int u;
scanf("%d", &u);
marked[u] = true;
}
for (int i = 1; i <= q; i++) {
int road, village;
scanf("%d %d", &road, &village);
queries[village].push_back({road, i});
}
dfs(e, e);
makeLCA();
it.init(1, 1, n);
solve(e, e);
for (int i = 1; i <= q; i++) {
if (ans[i] == -1) puts("escaped");
else {
if (ans[i] < (long long)1e16) printf("%lld\n", ans[i]);
else puts("oo");
}
}
return 0;
}
Compilation message
valley.cpp: In member function 'void SegmentTree::init(int, int, int)':
valley.cpp:23:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
valley.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
valley.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
valley.cpp: In member function 'long long int SegmentTree::query(int, int, int, int, int)':
valley.cpp:66:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
valley.cpp: In function 'int main()':
valley.cpp:147:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &n, &s, &q, &e); memset(par, -1, sizeof(par));
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &u);
~~~~~^~~~~~~~~~
valley.cpp:164:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &road, &village);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
13180 KB |
Output is correct |
2 |
Correct |
21 ms |
13304 KB |
Output is correct |
3 |
Correct |
21 ms |
13304 KB |
Output is correct |
4 |
Correct |
23 ms |
13304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
13180 KB |
Output is correct |
2 |
Correct |
21 ms |
13304 KB |
Output is correct |
3 |
Correct |
21 ms |
13304 KB |
Output is correct |
4 |
Correct |
23 ms |
13304 KB |
Output is correct |
5 |
Correct |
16 ms |
13048 KB |
Output is correct |
6 |
Correct |
16 ms |
13048 KB |
Output is correct |
7 |
Correct |
16 ms |
13048 KB |
Output is correct |
8 |
Correct |
16 ms |
13048 KB |
Output is correct |
9 |
Correct |
16 ms |
13052 KB |
Output is correct |
10 |
Correct |
16 ms |
13048 KB |
Output is correct |
11 |
Correct |
31 ms |
13048 KB |
Output is correct |
12 |
Correct |
17 ms |
13052 KB |
Output is correct |
13 |
Correct |
17 ms |
13176 KB |
Output is correct |
14 |
Correct |
16 ms |
13176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
513 ms |
32012 KB |
Output is correct |
2 |
Correct |
517 ms |
31624 KB |
Output is correct |
3 |
Correct |
577 ms |
31680 KB |
Output is correct |
4 |
Correct |
692 ms |
35164 KB |
Output is correct |
5 |
Correct |
540 ms |
34296 KB |
Output is correct |
6 |
Correct |
611 ms |
38652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
13180 KB |
Output is correct |
2 |
Correct |
21 ms |
13304 KB |
Output is correct |
3 |
Correct |
21 ms |
13304 KB |
Output is correct |
4 |
Correct |
23 ms |
13304 KB |
Output is correct |
5 |
Correct |
16 ms |
13048 KB |
Output is correct |
6 |
Correct |
16 ms |
13048 KB |
Output is correct |
7 |
Correct |
16 ms |
13048 KB |
Output is correct |
8 |
Correct |
16 ms |
13048 KB |
Output is correct |
9 |
Correct |
16 ms |
13052 KB |
Output is correct |
10 |
Correct |
16 ms |
13048 KB |
Output is correct |
11 |
Correct |
31 ms |
13048 KB |
Output is correct |
12 |
Correct |
17 ms |
13052 KB |
Output is correct |
13 |
Correct |
17 ms |
13176 KB |
Output is correct |
14 |
Correct |
16 ms |
13176 KB |
Output is correct |
15 |
Correct |
513 ms |
32012 KB |
Output is correct |
16 |
Correct |
517 ms |
31624 KB |
Output is correct |
17 |
Correct |
577 ms |
31680 KB |
Output is correct |
18 |
Correct |
692 ms |
35164 KB |
Output is correct |
19 |
Correct |
540 ms |
34296 KB |
Output is correct |
20 |
Correct |
611 ms |
38652 KB |
Output is correct |
21 |
Correct |
479 ms |
31336 KB |
Output is correct |
22 |
Correct |
529 ms |
31076 KB |
Output is correct |
23 |
Correct |
582 ms |
30956 KB |
Output is correct |
24 |
Correct |
705 ms |
35068 KB |
Output is correct |
25 |
Correct |
602 ms |
39680 KB |
Output is correct |
26 |
Correct |
481 ms |
31480 KB |
Output is correct |
27 |
Correct |
512 ms |
30968 KB |
Output is correct |
28 |
Correct |
859 ms |
31044 KB |
Output is correct |
29 |
Correct |
673 ms |
33664 KB |
Output is correct |
30 |
Correct |
610 ms |
35864 KB |
Output is correct |
31 |
Correct |
472 ms |
31508 KB |
Output is correct |
32 |
Correct |
490 ms |
31160 KB |
Output is correct |
33 |
Correct |
560 ms |
31136 KB |
Output is correct |
34 |
Correct |
709 ms |
34748 KB |
Output is correct |
35 |
Correct |
632 ms |
39672 KB |
Output is correct |
36 |
Correct |
720 ms |
34680 KB |
Output is correct |