# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
933677 |
2024-02-26T04:59:54 Z |
oblantis |
Valley (BOI19_valley) |
C++17 |
|
180 ms |
44488 KB |
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll inf = 1e15;
const int mod = 1e9+7;
const int maxn = 1e5 + 1;
vt<pii> g[maxn];
bool wt[maxn];
int n, s, q, e;
pair<int, ll> up[maxn][18];
ll p[maxn], dp[maxn], mi[maxn];
ll dfs(int v){
up[v][0].ss = inf;
mi[v] = inf;
if(wt[v])mi[v] = 0;
for(auto i : g[v]){
if(up[i.ff][0].ff)continue;
up[i.ff][0].ff = v;
dp[i.ff] = dp[v] + 1;
p[i.ff] = p[v] + i.ss;
mi[v] = min(mi[v], dfs(i.ff) + i.ss);
}
if(mi[v] != inf)mi[v] -= p[v];
for(auto i : g[v]){
if(up[v][0].ff == i.ff)continue;
up[i.ff][0].ss = mi[v];
}
if(mi[v] != inf)return mi[v] + p[v];
return inf;
}
void solve() {
cin >> n >> s >> q >> e;
int u[n], v[n], d[n];
for(int i = 1; i < n; i++){
cin >> u[i] >> v[i] >> d[i];
g[u[i]].pb({v[i], d[i]});
g[v[i]].pb({u[i], d[i]});
}
for(int i = 0, x; i < s; i++){
cin >> x;
wt[x] = 1;
}
up[e][0].ff = e;
dfs(e);
for(int i = 1; i < 18; i++){
for(int j = 1; j <= n; j++)up[j][i] = {up[up[j][i - 1].ff][i - 1].ff, min(up[j][i - 1].ss, up[up[j][i - 1].ff][i - 1].ss)};
}
for(int i = 1; i < n; i++){
if(dp[u[i]] > dp[v[i]])swap(u[i], v[i]);
}
for(int i = 0; i < q; i++){
int bl, we;
cin >> bl >> we;
int x = dp[we] - dp[v[bl]];
ll ms = mi[we], out = p[we];
if(x < 0){
cout << "escaped\n";
continue;
}
for(int o = 0; o < 18; o++){
if(x & 1){
ms = min(ms, up[we][o].ss);
we = up[we][o].ff;
}
x >>= 1;
}
if(we != v[bl]){
cout << "escaped\n";
continue;
}
if(ms == inf)cout << "oo\n";
else cout << out + ms << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int times = 1;
//cin >> times;
for(int i = 1; i <= times; i++) {
solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6492 KB |
Output is correct |
2 |
Correct |
3 ms |
6744 KB |
Output is correct |
3 |
Correct |
3 ms |
6492 KB |
Output is correct |
4 |
Correct |
4 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6492 KB |
Output is correct |
2 |
Correct |
3 ms |
6744 KB |
Output is correct |
3 |
Correct |
3 ms |
6492 KB |
Output is correct |
4 |
Correct |
4 ms |
6492 KB |
Output is correct |
5 |
Correct |
2 ms |
6492 KB |
Output is correct |
6 |
Correct |
3 ms |
6488 KB |
Output is correct |
7 |
Correct |
3 ms |
6488 KB |
Output is correct |
8 |
Correct |
2 ms |
6492 KB |
Output is correct |
9 |
Correct |
3 ms |
6492 KB |
Output is correct |
10 |
Correct |
3 ms |
6492 KB |
Output is correct |
11 |
Correct |
3 ms |
6492 KB |
Output is correct |
12 |
Correct |
2 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
6492 KB |
Output is correct |
14 |
Correct |
3 ms |
6488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
38912 KB |
Output is correct |
2 |
Correct |
107 ms |
38740 KB |
Output is correct |
3 |
Correct |
117 ms |
38536 KB |
Output is correct |
4 |
Correct |
170 ms |
40808 KB |
Output is correct |
5 |
Correct |
136 ms |
40784 KB |
Output is correct |
6 |
Correct |
126 ms |
43088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6492 KB |
Output is correct |
2 |
Correct |
3 ms |
6744 KB |
Output is correct |
3 |
Correct |
3 ms |
6492 KB |
Output is correct |
4 |
Correct |
4 ms |
6492 KB |
Output is correct |
5 |
Correct |
2 ms |
6492 KB |
Output is correct |
6 |
Correct |
3 ms |
6488 KB |
Output is correct |
7 |
Correct |
3 ms |
6488 KB |
Output is correct |
8 |
Correct |
2 ms |
6492 KB |
Output is correct |
9 |
Correct |
3 ms |
6492 KB |
Output is correct |
10 |
Correct |
3 ms |
6492 KB |
Output is correct |
11 |
Correct |
3 ms |
6492 KB |
Output is correct |
12 |
Correct |
2 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
6492 KB |
Output is correct |
14 |
Correct |
3 ms |
6488 KB |
Output is correct |
15 |
Correct |
95 ms |
38912 KB |
Output is correct |
16 |
Correct |
107 ms |
38740 KB |
Output is correct |
17 |
Correct |
117 ms |
38536 KB |
Output is correct |
18 |
Correct |
170 ms |
40808 KB |
Output is correct |
19 |
Correct |
136 ms |
40784 KB |
Output is correct |
20 |
Correct |
126 ms |
43088 KB |
Output is correct |
21 |
Correct |
78 ms |
39180 KB |
Output is correct |
22 |
Correct |
90 ms |
38836 KB |
Output is correct |
23 |
Correct |
99 ms |
38736 KB |
Output is correct |
24 |
Correct |
104 ms |
41176 KB |
Output is correct |
25 |
Correct |
147 ms |
44488 KB |
Output is correct |
26 |
Correct |
85 ms |
39236 KB |
Output is correct |
27 |
Correct |
104 ms |
38736 KB |
Output is correct |
28 |
Correct |
124 ms |
38764 KB |
Output is correct |
29 |
Correct |
116 ms |
40356 KB |
Output is correct |
30 |
Correct |
180 ms |
42124 KB |
Output is correct |
31 |
Correct |
91 ms |
39256 KB |
Output is correct |
32 |
Correct |
88 ms |
38836 KB |
Output is correct |
33 |
Correct |
93 ms |
38740 KB |
Output is correct |
34 |
Correct |
126 ms |
40984 KB |
Output is correct |
35 |
Correct |
130 ms |
44208 KB |
Output is correct |
36 |
Correct |
129 ms |
41676 KB |
Output is correct |