# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
766542 |
2023-06-25T19:42:19 Z |
BeanZ |
Valley (BOI19_valley) |
C++14 |
|
259 ms |
58376 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e5 + 5;
long long mod = 998244353;
const int lim = 4e5 + 5;
const int lg = 22;
const int base = 311;
const long double eps = 1e-6;
struct viet{
ll u, v, w;
};
vector<viet> E;
ll dp[N][lg + 1], par[N][lg + 1], dep[N], a[N], dep2[N];
vector<pair<ll, ll>> node[N];
void dfs2(ll u, ll p){
for (int i = 1; i <= lg; i++){
dp[u][i] = min(dp[u][i - 1], dp[par[u][i - 1]][i - 1]);
}
for (auto j : node[u]){
if (j.first == p) continue;
dfs2(j.first, u);
}
}
void dfs(ll u, ll p){
for (int i = 1; i <= lg; i++){
par[u][i] = par[par[u][i - 1]][i - 1];
}
dp[u][0] = 1e18;
for (auto j : node[u]){
if (j.first == p) continue;
par[j.first][0] = u;
dep[j.first] = dep[u] + j.second;
dep2[j.first] = dep2[u] + 1;
dfs(j.first, u);
dp[u][0] = min(dp[u][0], dp[j.first][0] + j.second * 2);
}
if (a[u]) dp[u][0] = -dep[u];
}
ll check(ll u, ll v){
ll dist = dep2[v] - dep2[u];
if (dist < 0) return 0;
for (int i = 0; i <= lg; i++){
if (dist & (1 << i)){
v = par[v][i];
}
}
if (v == u) return 1;
else return 0;
}
ll get(ll u, ll v){
ll dist = dep2[u] - dep2[v];
ll res = 1e18;
ll dd = dep[u];
for (int i = 0; i <= lg; i++){
if (dist & (1 << i)){
res = min(res, dd + dp[u][i]);
u = par[u][i];
}
}
res = min(res, dd + dp[u][0]);
return res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("tests.inp", "r")){
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll n, s, q, e;
cin >> n >> s >> q >> e;
for (int i = 1; i < n; i++){
ll u, v, w;
cin >> u >> v >> w;
E.push_back({u, v, w});
node[u].push_back({v, w});
node[v].push_back({u, w});
}
for (int i = 1; i <= s; i++){
ll x;
cin >> x;
a[x] = 1;
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= lg; j++){
dp[i][j] = 1e18;
}
}
dfs(e, e);
dfs2(e, e);
while (q--){
ll u, v;
cin >> v >> u;
ll n1 = E[v - 1].u;
ll n2 = E[v - 1].v;
if (dep[n1] < dep[n2]) swap(n1, n2);
if (!check(n1, u)) cout << "escaped" << endl;
else {
ll x = get(u, n1);
if (x > 1e17) cout << "oo" << endl;
else cout << x << endl;
}
}
}
/*
Ans:
Out:
*/
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | freopen("test.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | freopen("test.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2772 KB |
Output is correct |
2 |
Correct |
5 ms |
2900 KB |
Output is correct |
3 |
Correct |
4 ms |
2772 KB |
Output is correct |
4 |
Correct |
4 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2772 KB |
Output is correct |
2 |
Correct |
5 ms |
2900 KB |
Output is correct |
3 |
Correct |
4 ms |
2772 KB |
Output is correct |
4 |
Correct |
4 ms |
2772 KB |
Output is correct |
5 |
Correct |
3 ms |
3200 KB |
Output is correct |
6 |
Correct |
2 ms |
3156 KB |
Output is correct |
7 |
Correct |
2 ms |
3204 KB |
Output is correct |
8 |
Correct |
2 ms |
3156 KB |
Output is correct |
9 |
Correct |
3 ms |
3200 KB |
Output is correct |
10 |
Correct |
3 ms |
3156 KB |
Output is correct |
11 |
Correct |
2 ms |
3156 KB |
Output is correct |
12 |
Correct |
3 ms |
3212 KB |
Output is correct |
13 |
Correct |
3 ms |
3156 KB |
Output is correct |
14 |
Correct |
3 ms |
3200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
154 ms |
52912 KB |
Output is correct |
2 |
Correct |
201 ms |
52788 KB |
Output is correct |
3 |
Correct |
188 ms |
52976 KB |
Output is correct |
4 |
Correct |
221 ms |
55276 KB |
Output is correct |
5 |
Correct |
217 ms |
55396 KB |
Output is correct |
6 |
Correct |
259 ms |
57968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2772 KB |
Output is correct |
2 |
Correct |
5 ms |
2900 KB |
Output is correct |
3 |
Correct |
4 ms |
2772 KB |
Output is correct |
4 |
Correct |
4 ms |
2772 KB |
Output is correct |
5 |
Correct |
3 ms |
3200 KB |
Output is correct |
6 |
Correct |
2 ms |
3156 KB |
Output is correct |
7 |
Correct |
2 ms |
3204 KB |
Output is correct |
8 |
Correct |
2 ms |
3156 KB |
Output is correct |
9 |
Correct |
3 ms |
3200 KB |
Output is correct |
10 |
Correct |
3 ms |
3156 KB |
Output is correct |
11 |
Correct |
2 ms |
3156 KB |
Output is correct |
12 |
Correct |
3 ms |
3212 KB |
Output is correct |
13 |
Correct |
3 ms |
3156 KB |
Output is correct |
14 |
Correct |
3 ms |
3200 KB |
Output is correct |
15 |
Correct |
154 ms |
52912 KB |
Output is correct |
16 |
Correct |
201 ms |
52788 KB |
Output is correct |
17 |
Correct |
188 ms |
52976 KB |
Output is correct |
18 |
Correct |
221 ms |
55276 KB |
Output is correct |
19 |
Correct |
217 ms |
55396 KB |
Output is correct |
20 |
Correct |
259 ms |
57968 KB |
Output is correct |
21 |
Correct |
151 ms |
51508 KB |
Output is correct |
22 |
Correct |
166 ms |
51288 KB |
Output is correct |
23 |
Correct |
219 ms |
51496 KB |
Output is correct |
24 |
Correct |
231 ms |
54056 KB |
Output is correct |
25 |
Correct |
224 ms |
57032 KB |
Output is correct |
26 |
Correct |
164 ms |
51996 KB |
Output is correct |
27 |
Correct |
215 ms |
51792 KB |
Output is correct |
28 |
Correct |
176 ms |
52088 KB |
Output is correct |
29 |
Correct |
207 ms |
53788 KB |
Output is correct |
30 |
Correct |
234 ms |
55760 KB |
Output is correct |
31 |
Correct |
150 ms |
52520 KB |
Output is correct |
32 |
Correct |
169 ms |
52428 KB |
Output is correct |
33 |
Correct |
184 ms |
52696 KB |
Output is correct |
34 |
Correct |
208 ms |
54940 KB |
Output is correct |
35 |
Correct |
236 ms |
58376 KB |
Output is correct |
36 |
Correct |
192 ms |
54920 KB |
Output is correct |