# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
382058 |
2021-03-26T10:36:20 Z |
rocks03 |
Valley (BOI19_valley) |
C++14 |
|
227 ms |
51692 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Edge{
int u, w, i;
};
const int MAXN = 2e5+100;
int N, S, Q, E, shop[MAXN];
pii edge[MAXN];
vector<Edge> g[MAXN];
int timer, tin[MAXN], tou[MAXN];
const int MAXK = 20+5;
int depth[MAXN], pa[MAXK][MAXN];
bool is_shop[MAXN];
ll dist[MAXN], min_dist[MAXN], value[MAXN], answer[MAXK][MAXN];
void dfs(int v, int p){
tin[v] = timer++;
pa[0][v] = p;
min_dist[v] = LLONG_MAX;
if(is_shop[v]) min_dist[v] = dist[v];
for(auto [u, w, i] : g[v]){
if(u != p){
depth[u] = depth[v] + 1;
dist[u] = dist[v] + w;
dfs(u, v);
if(min_dist[u] != LLONG_MAX){
min_dist[v] = min(min_dist[v], min_dist[u]);
}
}
}
tou[v] = timer - 1;
value[v] = LLONG_MAX;
if(min_dist[v] != LLONG_MAX){
value[v] = min_dist[v] - 2 * dist[v];
}
}
bool is_ancestor(int u, int v){
return (tin[u] <= tin[v] && tou[v] <= tou[u]);
}
void solve(){
cin >> N >> S >> Q >> E;
--E;
rep(i, 0, N - 1){
int u, v, w;
cin >> u >> v >> w;
--u, --v;
g[u].pb({v, w, i});
g[v].pb({u, w, i});
edge[i] = {u, v};
}
rep(i, 0, S){
cin >> shop[i];
--shop[i];
is_shop[shop[i]] = true;
}
dfs(E, -1);
rep(v, 0, N){
if(pa[0][v] == -1){
answer[0][v] = value[v];
} else{
answer[0][v] = min(value[v], value[pa[0][v]]);
}
}
rep(k, 0, MAXK - 1){
rep(i, 0, N){
if(pa[k][i] == -1){
pa[k + 1][i] = -1;
answer[k + 1][i] = answer[k][i];
} else{
pa[k + 1][i] = pa[k][pa[k][i]];
answer[k + 1][i] = min(answer[k][i], answer[k][pa[k][i]]);
}
}
}
rep(q, 0, Q){
int i, x;
cin >> i >> x;
--i, --x;
auto [u, v] = edge[i];
if(is_ancestor(u, x) && is_ancestor(v, x)){
int lca = is_ancestor(u, v) ? v : u;
int diff = depth[x] - depth[lca];
ll cur = dist[x];
ll ans = LLONG_MAX;
if(value[x] != LLONG_MAX) ans = cur + value[x];
per(k, MAXK - 1, 0){
if(diff >> k & 1){
if(answer[k][x] != LLONG_MAX)
ans = min(ans, cur + answer[k][x]);
x = pa[k][x];
}
}
if(ans == LLONG_MAX){
cout << "oo\n";
} else{
cout << ans << "\n";
}
} else{
cout << "escaped\n";
}
}
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(nullptr);
solve();
return 0;
}
Compilation message
valley.cpp: In function 'void dfs(int, int)':
valley.cpp:37:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
37 | for(auto [u, w, i] : g[v]){
| ^
valley.cpp: In function 'void solve()':
valley.cpp:97:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
97 | auto [u, v] = edge[i];
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5484 KB |
Output is correct |
2 |
Correct |
8 ms |
5484 KB |
Output is correct |
3 |
Correct |
7 ms |
5484 KB |
Output is correct |
4 |
Correct |
8 ms |
5484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5484 KB |
Output is correct |
2 |
Correct |
8 ms |
5484 KB |
Output is correct |
3 |
Correct |
7 ms |
5484 KB |
Output is correct |
4 |
Correct |
8 ms |
5484 KB |
Output is correct |
5 |
Correct |
5 ms |
5868 KB |
Output is correct |
6 |
Correct |
5 ms |
5740 KB |
Output is correct |
7 |
Correct |
5 ms |
5868 KB |
Output is correct |
8 |
Correct |
5 ms |
5868 KB |
Output is correct |
9 |
Correct |
5 ms |
5740 KB |
Output is correct |
10 |
Correct |
6 ms |
5868 KB |
Output is correct |
11 |
Correct |
6 ms |
5868 KB |
Output is correct |
12 |
Correct |
5 ms |
5740 KB |
Output is correct |
13 |
Correct |
6 ms |
5868 KB |
Output is correct |
14 |
Correct |
5 ms |
5868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
156 ms |
44600 KB |
Output is correct |
2 |
Correct |
160 ms |
44268 KB |
Output is correct |
3 |
Correct |
176 ms |
44140 KB |
Output is correct |
4 |
Correct |
192 ms |
45932 KB |
Output is correct |
5 |
Correct |
165 ms |
46060 KB |
Output is correct |
6 |
Correct |
219 ms |
47596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5484 KB |
Output is correct |
2 |
Correct |
8 ms |
5484 KB |
Output is correct |
3 |
Correct |
7 ms |
5484 KB |
Output is correct |
4 |
Correct |
8 ms |
5484 KB |
Output is correct |
5 |
Correct |
5 ms |
5868 KB |
Output is correct |
6 |
Correct |
5 ms |
5740 KB |
Output is correct |
7 |
Correct |
5 ms |
5868 KB |
Output is correct |
8 |
Correct |
5 ms |
5868 KB |
Output is correct |
9 |
Correct |
5 ms |
5740 KB |
Output is correct |
10 |
Correct |
6 ms |
5868 KB |
Output is correct |
11 |
Correct |
6 ms |
5868 KB |
Output is correct |
12 |
Correct |
5 ms |
5740 KB |
Output is correct |
13 |
Correct |
6 ms |
5868 KB |
Output is correct |
14 |
Correct |
5 ms |
5868 KB |
Output is correct |
15 |
Correct |
156 ms |
44600 KB |
Output is correct |
16 |
Correct |
160 ms |
44268 KB |
Output is correct |
17 |
Correct |
176 ms |
44140 KB |
Output is correct |
18 |
Correct |
192 ms |
45932 KB |
Output is correct |
19 |
Correct |
165 ms |
46060 KB |
Output is correct |
20 |
Correct |
219 ms |
47596 KB |
Output is correct |
21 |
Correct |
138 ms |
45164 KB |
Output is correct |
22 |
Correct |
157 ms |
47212 KB |
Output is correct |
23 |
Correct |
180 ms |
46956 KB |
Output is correct |
24 |
Correct |
186 ms |
48964 KB |
Output is correct |
25 |
Correct |
181 ms |
51692 KB |
Output is correct |
26 |
Correct |
143 ms |
47596 KB |
Output is correct |
27 |
Correct |
144 ms |
47212 KB |
Output is correct |
28 |
Correct |
173 ms |
47084 KB |
Output is correct |
29 |
Correct |
180 ms |
48364 KB |
Output is correct |
30 |
Correct |
227 ms |
49900 KB |
Output is correct |
31 |
Correct |
140 ms |
47724 KB |
Output is correct |
32 |
Correct |
152 ms |
47340 KB |
Output is correct |
33 |
Correct |
162 ms |
47340 KB |
Output is correct |
34 |
Correct |
188 ms |
49004 KB |
Output is correct |
35 |
Correct |
193 ms |
51692 KB |
Output is correct |
36 |
Correct |
192 ms |
49516 KB |
Output is correct |