#include <bits/stdc++.h>
#define mp make_pair
#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const int K = 20;
struct info {
ll length, min_cost, top_node;
info() {length=0,min_cost=0;}
info(ll a, ll b, ll c) {length = a, min_cost = b, top_node = c;}
};
info merge(info lower, info higher) {
return info(lower.length + higher.length, min(lower.min_cost, higher.min_cost + lower.length), higher.top_node);
}
vector<pair<pii, ll> > edges;
vector<vector<pii> > graph;
vector<vector<info> > lift;
vector<int> in_time;
vector<int> out_time;
vector<bool> is_shop;
int tim = 0;
ll dfs(int curr, ll par, ll edge_cst) {
ll min_cost = 1e18;
if (is_shop[curr])
min_cost = 0;
in_time[curr] = tim;
for (auto &[a, w] : graph[curr]) {
if (a == par)
continue;
tim++;
min_cost = min(min_cost, dfs(a, curr, w) + w);
}
lift[0][curr] = info(edge_cst, min_cost, par);
out_time[curr] = ++tim;
return min_cost;
}
void dfs2(int curr, ll par) {
for (int i = 1; i < K; i++)
lift[i][curr] = merge(lift[i - 1][curr], lift[i-1][lift[i-1][curr].top_node]);
for (auto &[a, w] : graph[curr])
if (a != par)
dfs2(a, curr);
}
bool is_ancestor(int a, int b) {
return in_time[a] <= in_time[b] and out_time[a] >= out_time[b];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, s, q, e;
cin >> n >> s >> q >> e;
graph = vector<vector<pii> > (n+1);
in_time.resize(n+1);
in_time[0] = -1e9;
out_time.resize(n+1);
out_time[0] = 1e9;
edges.resize(n+1);
is_shop.resize(n+1);
lift.resize(K, vector<info>(n+1));
for (int i = 0; i < n - 1; i++) {
cin >> edges[i].first.first >> edges[i].first.second >> edges[i].second;
graph[edges[i].first.first].push_back({edges[i].first.second, edges[i].second});
graph[edges[i].first.second].push_back({edges[i].first.first, edges[i].second});
}
for (int i = 0; i < s; i++) {
int guy;
cin >> guy;
is_shop[guy] = true;
}
dfs(e, 0, 0);
dfs2(e, 0);
while (q--) {
int block, r;
cin >> block >> r;
block--;
pii block_edge = edges[block].first;
if (in_time[block_edge.first] < in_time[block_edge.second])
swap(block_edge.first, block_edge.second);
int block_node = block_edge.first;
// checking if you can leave
if (!is_ancestor(block_node, r)) {
cout << "escaped\n";
continue;
}
block_node = lift[0][block_edge.second].top_node;
// now_bin_lifting
info ans = lift[0][r];
for (int i = K - 1; i >= 0; i--) {
info top = lift[i][ans.top_node];
if (is_ancestor(top.top_node, block_node))
continue;
ans = merge(ans, top);
}
if (ans.min_cost >= 1e18)
cout << "oo\n";
else
cout << ans.min_cost << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
456 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
456 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
844 KB |
Output is correct |
6 |
Correct |
2 ms |
896 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
852 KB |
Output is correct |
10 |
Correct |
1 ms |
852 KB |
Output is correct |
11 |
Correct |
2 ms |
844 KB |
Output is correct |
12 |
Correct |
2 ms |
852 KB |
Output is correct |
13 |
Correct |
1 ms |
852 KB |
Output is correct |
14 |
Correct |
2 ms |
852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
168 ms |
59484 KB |
Output is correct |
2 |
Correct |
191 ms |
62240 KB |
Output is correct |
3 |
Correct |
200 ms |
62468 KB |
Output is correct |
4 |
Correct |
224 ms |
64308 KB |
Output is correct |
5 |
Correct |
190 ms |
64472 KB |
Output is correct |
6 |
Correct |
249 ms |
66596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
456 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
844 KB |
Output is correct |
6 |
Correct |
2 ms |
896 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
852 KB |
Output is correct |
10 |
Correct |
1 ms |
852 KB |
Output is correct |
11 |
Correct |
2 ms |
844 KB |
Output is correct |
12 |
Correct |
2 ms |
852 KB |
Output is correct |
13 |
Correct |
1 ms |
852 KB |
Output is correct |
14 |
Correct |
2 ms |
852 KB |
Output is correct |
15 |
Correct |
168 ms |
59484 KB |
Output is correct |
16 |
Correct |
191 ms |
62240 KB |
Output is correct |
17 |
Correct |
200 ms |
62468 KB |
Output is correct |
18 |
Correct |
224 ms |
64308 KB |
Output is correct |
19 |
Correct |
190 ms |
64472 KB |
Output is correct |
20 |
Correct |
249 ms |
66596 KB |
Output is correct |
21 |
Correct |
165 ms |
61876 KB |
Output is correct |
22 |
Correct |
177 ms |
61732 KB |
Output is correct |
23 |
Correct |
206 ms |
61984 KB |
Output is correct |
24 |
Correct |
238 ms |
63956 KB |
Output is correct |
25 |
Correct |
218 ms |
66996 KB |
Output is correct |
26 |
Correct |
174 ms |
61848 KB |
Output is correct |
27 |
Correct |
192 ms |
61652 KB |
Output is correct |
28 |
Correct |
196 ms |
61948 KB |
Output is correct |
29 |
Correct |
244 ms |
63396 KB |
Output is correct |
30 |
Correct |
241 ms |
64964 KB |
Output is correct |
31 |
Correct |
164 ms |
61868 KB |
Output is correct |
32 |
Correct |
179 ms |
61732 KB |
Output is correct |
33 |
Correct |
191 ms |
62084 KB |
Output is correct |
34 |
Correct |
236 ms |
63892 KB |
Output is correct |
35 |
Correct |
223 ms |
66852 KB |
Output is correct |
36 |
Correct |
208 ms |
63908 KB |
Output is correct |