# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
784118 |
2023-07-15T17:49:05 Z |
raysh07 |
Valley (BOI19_valley) |
C++17 |
|
144 ms |
53712 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int n, s, q, r;
const int N = 1e5 + 69;
vector <pair<int, int>> adj[N];
int dp[N], l1[N][20], l2[N][20], tin[N], tout[N], d[N], ok1[N], timer = 0;
bool ok[N];
void dfs(int u, int p){
dp[u] = INF;
tin[u] = ++timer;
if (ok[u]) dp[u] = 0;
for (auto [v, w] : adj[u]){
if (v != p){
l2[v][0] = u;
d[v] = d[u] + w;
ok1[v] = ok1[u] + 1;
dfs(v, u);
dp[u] = min(dp[u], dp[v] + w);
}
}
tout[u] = timer;
}
void Solve()
{
cin >> n >> s >> q >> r;
vector <pair<int, int>> e;
for (int i = 1; i < n; i++){
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
e.push_back({u, v});
}
while (s--){
int x; cin >> x;
ok[x] = true;
}
dfs(r, -1);
for (int i = 1; i <= n; i++){
l1[i][0] = dp[i];
}
for (int j = 1; j < 20; j++){
for (int i = 1; i <= n; i++){
l2[i][j] = l2[l2[i][j - 1]][j - 1];
int x = l2[i][j - 1];
if (x == 0) continue;
l1[i][j] = min(l1[i][j - 1], l1[x][j - 1] + d[i] - d[x]);
}
}
while (q--){
int id, x; cin >> id >> x;
--id;
if (d[e[id].first] < d[e[id].second]) swap(e[id].first, e[id].second);
int u = e[id].first;
int v = e[id].second;
if (tin[u] <= tin[x] && tout[u] >= tout[x]){
int ans = INF;
int add = 0;
int lol = ok1[x] - ok1[v];
// cout << lol << "\n";
for (int i = 0; i < 20; i++){
if (lol >> i & 1){
ans = min(ans, add + l1[x][i]);
add += d[x] - d[l2[x][i]];
x = l2[x][i];
}
}
if (ans == INF) cout << "oo\n";
else cout << ans << "\n";
} else {
cout << "escaped\n";
}
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2824 KB |
Output is correct |
2 |
Correct |
3 ms |
2820 KB |
Output is correct |
3 |
Correct |
3 ms |
2900 KB |
Output is correct |
4 |
Correct |
3 ms |
2820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2824 KB |
Output is correct |
2 |
Correct |
3 ms |
2820 KB |
Output is correct |
3 |
Correct |
3 ms |
2900 KB |
Output is correct |
4 |
Correct |
3 ms |
2820 KB |
Output is correct |
5 |
Correct |
2 ms |
3076 KB |
Output is correct |
6 |
Correct |
2 ms |
3156 KB |
Output is correct |
7 |
Correct |
2 ms |
3156 KB |
Output is correct |
8 |
Correct |
2 ms |
3080 KB |
Output is correct |
9 |
Correct |
3 ms |
3156 KB |
Output is correct |
10 |
Correct |
2 ms |
3156 KB |
Output is correct |
11 |
Correct |
2 ms |
3156 KB |
Output is correct |
12 |
Correct |
3 ms |
3080 KB |
Output is correct |
13 |
Correct |
2 ms |
3156 KB |
Output is correct |
14 |
Correct |
3 ms |
3144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
122 ms |
49268 KB |
Output is correct |
2 |
Correct |
110 ms |
48968 KB |
Output is correct |
3 |
Correct |
119 ms |
49256 KB |
Output is correct |
4 |
Correct |
136 ms |
51140 KB |
Output is correct |
5 |
Correct |
126 ms |
51176 KB |
Output is correct |
6 |
Correct |
144 ms |
53388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2824 KB |
Output is correct |
2 |
Correct |
3 ms |
2820 KB |
Output is correct |
3 |
Correct |
3 ms |
2900 KB |
Output is correct |
4 |
Correct |
3 ms |
2820 KB |
Output is correct |
5 |
Correct |
2 ms |
3076 KB |
Output is correct |
6 |
Correct |
2 ms |
3156 KB |
Output is correct |
7 |
Correct |
2 ms |
3156 KB |
Output is correct |
8 |
Correct |
2 ms |
3080 KB |
Output is correct |
9 |
Correct |
3 ms |
3156 KB |
Output is correct |
10 |
Correct |
2 ms |
3156 KB |
Output is correct |
11 |
Correct |
2 ms |
3156 KB |
Output is correct |
12 |
Correct |
3 ms |
3080 KB |
Output is correct |
13 |
Correct |
2 ms |
3156 KB |
Output is correct |
14 |
Correct |
3 ms |
3144 KB |
Output is correct |
15 |
Correct |
122 ms |
49268 KB |
Output is correct |
16 |
Correct |
110 ms |
48968 KB |
Output is correct |
17 |
Correct |
119 ms |
49256 KB |
Output is correct |
18 |
Correct |
136 ms |
51140 KB |
Output is correct |
19 |
Correct |
126 ms |
51176 KB |
Output is correct |
20 |
Correct |
144 ms |
53388 KB |
Output is correct |
21 |
Correct |
95 ms |
48520 KB |
Output is correct |
22 |
Correct |
106 ms |
48324 KB |
Output is correct |
23 |
Correct |
116 ms |
48540 KB |
Output is correct |
24 |
Correct |
130 ms |
50660 KB |
Output is correct |
25 |
Correct |
140 ms |
53712 KB |
Output is correct |
26 |
Correct |
98 ms |
48608 KB |
Output is correct |
27 |
Correct |
102 ms |
48420 KB |
Output is correct |
28 |
Correct |
114 ms |
48676 KB |
Output is correct |
29 |
Correct |
133 ms |
50216 KB |
Output is correct |
30 |
Correct |
141 ms |
51768 KB |
Output is correct |
31 |
Correct |
101 ms |
48780 KB |
Output is correct |
32 |
Correct |
111 ms |
48568 KB |
Output is correct |
33 |
Correct |
116 ms |
48880 KB |
Output is correct |
34 |
Correct |
134 ms |
50696 KB |
Output is correct |
35 |
Correct |
138 ms |
53684 KB |
Output is correct |
36 |
Correct |
125 ms |
50668 KB |
Output is correct |