# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1004023 |
2024-06-21T01:13:09 Z |
May27_th |
Valley (BOI19_valley) |
C++17 |
|
141 ms |
44532 KB |
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
const i64 INF = 1e18;
const int MAXN = 100015;
int villages, shops, Q, exitP, h[MAXN], up[MAXN][22];
int counter = 0, tin[MAXN], tout[MAXN];
i64 d[MAXN], mind[MAXN], upd[MAXN][22];
bool isShop[MAXN];
pair<int, int> Edges[MAXN];
vector<pair<int, int>> G[MAXN];
void dfs(int u) {
tin[u] = tout[u] = ++counter;
if (isShop[u]) mind[u] = d[u];
else mind[u] = INF;
for (auto [v, w] : G[u]) {
if (v != up[u][0]) {
up[v][0] = u;
d[v] = d[u] + w;
h[v] = h[u] + 1;
for (int j = 1; j <= 20; j ++) {
up[v][j] = up[up[v][j - 1]][j - 1];
}
dfs(v);
mind[u] = min(mind[u], mind[v]);
}
}
tout[u] = counter;
}
void dfs1(int u) {
for (auto [v, w] : G[u]) {
if (v != up[u][0]) {
upd[v][0] = mind[u];
for (int j = 1; j <= 20; j ++) {
upd[v][j] = min(upd[v][j - 1], upd[up[v][j - 1]][j - 1]);
}
dfs1(v);
}
}
}
void Solve (void) {
cin >> villages >> shops >> Q >> exitP;
for (int i = 1; i <= villages; i ++) isShop[i] = false;
for (int i = 1; i < villages; i ++) {
int u, v, w; cin >> u >> v >> w;
G[u].pb(mp(v, w));
G[v].pb(mp(u, w));
Edges[i] = mp(u, v);
}
for (int i = 1; i <= shops; i ++) {
int x; cin >> x;
isShop[x] = true;
}
dfs(exitP);
for (int i = 1; i <= villages; i ++) {
if (mind[i] != INF) mind[i] = mind[i] - 2 * d[i];
}
dfs1(exitP);
while (Q --) {
int RoadID, st; cin >> RoadID >> st;
auto [u, v] = Edges[RoadID];
if (h[v] < h[u]) swap(u, v);
if (tin[v] <= tin[st] && tout[st] <= tout[v]) {
// Lie in subtree
int gap = h[st] - h[v];
i64 mn = mind[st], add = d[st];
for (int j = 20; j >= 0; j --) {
if (gap >> j & 1) {
mn = min(mn, upd[st][j]);
st = up[st][j];
}
}
if (mn >= INF) cout << "oo" << "\n";
else cout << mn + add << "\n";
} else {
cout << "escaped" << "\n";
}
}
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
// Prepare();
int Tests = 1; // cin >> Tests;
while (Tests --) {
Solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2904 KB |
Output is correct |
2 |
Correct |
3 ms |
2908 KB |
Output is correct |
3 |
Correct |
3 ms |
2824 KB |
Output is correct |
4 |
Correct |
3 ms |
2968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2904 KB |
Output is correct |
2 |
Correct |
3 ms |
2908 KB |
Output is correct |
3 |
Correct |
3 ms |
2824 KB |
Output is correct |
4 |
Correct |
3 ms |
2968 KB |
Output is correct |
5 |
Correct |
2 ms |
3164 KB |
Output is correct |
6 |
Correct |
2 ms |
3164 KB |
Output is correct |
7 |
Correct |
2 ms |
3164 KB |
Output is correct |
8 |
Correct |
2 ms |
3152 KB |
Output is correct |
9 |
Correct |
2 ms |
3164 KB |
Output is correct |
10 |
Correct |
2 ms |
3160 KB |
Output is correct |
11 |
Correct |
2 ms |
3164 KB |
Output is correct |
12 |
Correct |
2 ms |
3164 KB |
Output is correct |
13 |
Correct |
2 ms |
3164 KB |
Output is correct |
14 |
Correct |
2 ms |
3240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
101 ms |
40436 KB |
Output is correct |
2 |
Correct |
96 ms |
40276 KB |
Output is correct |
3 |
Correct |
108 ms |
40032 KB |
Output is correct |
4 |
Correct |
118 ms |
41812 KB |
Output is correct |
5 |
Correct |
106 ms |
42148 KB |
Output is correct |
6 |
Correct |
131 ms |
43868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2904 KB |
Output is correct |
2 |
Correct |
3 ms |
2908 KB |
Output is correct |
3 |
Correct |
3 ms |
2824 KB |
Output is correct |
4 |
Correct |
3 ms |
2968 KB |
Output is correct |
5 |
Correct |
2 ms |
3164 KB |
Output is correct |
6 |
Correct |
2 ms |
3164 KB |
Output is correct |
7 |
Correct |
2 ms |
3164 KB |
Output is correct |
8 |
Correct |
2 ms |
3152 KB |
Output is correct |
9 |
Correct |
2 ms |
3164 KB |
Output is correct |
10 |
Correct |
2 ms |
3160 KB |
Output is correct |
11 |
Correct |
2 ms |
3164 KB |
Output is correct |
12 |
Correct |
2 ms |
3164 KB |
Output is correct |
13 |
Correct |
2 ms |
3164 KB |
Output is correct |
14 |
Correct |
2 ms |
3240 KB |
Output is correct |
15 |
Correct |
101 ms |
40436 KB |
Output is correct |
16 |
Correct |
96 ms |
40276 KB |
Output is correct |
17 |
Correct |
108 ms |
40032 KB |
Output is correct |
18 |
Correct |
118 ms |
41812 KB |
Output is correct |
19 |
Correct |
106 ms |
42148 KB |
Output is correct |
20 |
Correct |
131 ms |
43868 KB |
Output is correct |
21 |
Correct |
110 ms |
39928 KB |
Output is correct |
22 |
Correct |
112 ms |
39740 KB |
Output is correct |
23 |
Correct |
97 ms |
39684 KB |
Output is correct |
24 |
Correct |
108 ms |
41552 KB |
Output is correct |
25 |
Correct |
121 ms |
44532 KB |
Output is correct |
26 |
Correct |
87 ms |
40016 KB |
Output is correct |
27 |
Correct |
103 ms |
39712 KB |
Output is correct |
28 |
Correct |
109 ms |
39504 KB |
Output is correct |
29 |
Correct |
112 ms |
40964 KB |
Output is correct |
30 |
Correct |
141 ms |
42592 KB |
Output is correct |
31 |
Correct |
89 ms |
40016 KB |
Output is correct |
32 |
Correct |
90 ms |
39892 KB |
Output is correct |
33 |
Correct |
101 ms |
39760 KB |
Output is correct |
34 |
Correct |
117 ms |
41552 KB |
Output is correct |
35 |
Correct |
123 ms |
44368 KB |
Output is correct |
36 |
Correct |
111 ms |
41376 KB |
Output is correct |