# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
659495 |
2022-11-18T09:28:23 Z |
Ronin13 |
Valley (BOI19_valley) |
C++14 |
|
393 ms |
40244 KB |
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
const int nmax = 2e5 + 1;
vector <vector <ll> > t(nmax);
vector <vector <pii> > g(nmax);
vector <vector <int> > path(nmax);
vector <int> lead(nmax);
vector <int> p(nmax);
vector <int> sz(nmax);
vector <ll> d(nmax);
vector <ll> dp(nmax, 2e18);
vector <bool> shop(nmax);
vector <int> pp(nmax);
vector <int> in(nmax);
int timer = 1;
void dfs(int v, int e = 0){
sz[v] = 1;
p[v] = e;
in[v] = timer++;
for(auto x : g[v]){
int to = x.f;
ll len = x.s;
if(to == e) continue;
d[to] = d[v] + len;
dfs(to, v);
dp[v] = min(dp[v], dp[to] + len);
sz[v] += sz[to];
}
if(shop[v]) dp[v] = 0;
}
void decompose(int v, int head, int e = 0){
path[head].pb(v);
pp[v] = path[head].size();
lead[v] = head;
for(auto x : g[v]){
int to = x.f;
if(to == e) continue;
if(2 * sz[to] >= sz[v]) decompose(to, head, v);
else decompose(to, to, v);
}
}
void update(int v, int l, int r, int pos, int ind, ll val){
if(pos > r || pos < l) return;
if(l == r){
t[ind][v] = min((ll)1e18, val);
return;
}
int m = (l + r) / 2;
update(2 * v, l, m, pos, ind, val);
update(2 * v + 1, m + 1, r, pos, ind, val);
t[ind][v] = min(t[ind][2 * v], t[ind][2 * v + 1]);
}
ll get(int v, int l, int r, int st, int fin, int ind){
if(l > fin || r < st) return 1e18;
if(l >= st && r <= fin) {
return t[ind][v];
}
int m = (l + r) / 2;
return min(get(2 * v, l, m, st, fin, ind),
get(2 * v + 1, m + 1, r, st, fin, ind));
}
void build(int n){
for(int i = 1; i <= n; i++){
t[i].resize(path[i].size() * 4);
}
for(int i= 1; i <= n; i++){
update(1, 1, path[lead[i]].size(), pp[i], lead[i], -d[i] + dp[i]);
}
}
ll lift(ll x, ll y){
ll ans = 1e18;
while(lead[x] != lead[y]){
int v = lead[x];
ans = min(ans, get(1, 1, path[v].size(), pp[v], pp[x], v));
x = p[v];
}
int v = lead[x];
ans = min(ans, get(1, 1, path[v].size(), pp[y], pp[x], v));
return ans;
}
int main(){
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
int n, s, q, e;
cin >> n >> s >> q >> e;
int edge[n];
vector <pii> edges;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
ll w; cin >> w;
edges.pb({u, v});
g[u].pb({v, w});
g[v].pb({u, w});
}
for(int i = 1; i <= s; i++){
int x; cin >> x;
shop[x] = true;
}
dfs(e);
decompose(e, e);
/* for(int i = 1; i <= n; i++)
cout << lead[i] << ' ';*/
for(int i = 1; i < n; i++){
int x = edges[i - 1].f, y = edges[i - 1].s;
if(p[x] == y){
edge[i] = x;
}
else edge[i] = y;
}
build(n);
while(q--){
int x, r; cin >> x >> r;
int v = edge[x];
if(in[v] > in[r] || (in[v] + sz[v] < in[r] + sz[r])) {
cout << "escaped\n";
continue;
}
ll D = lift(r, v);
if(D == 1e18){
cout << "oo\n";
continue;
}
cout << D + d[r] << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
21588 KB |
Output is correct |
2 |
Correct |
27 ms |
21580 KB |
Output is correct |
3 |
Correct |
27 ms |
21536 KB |
Output is correct |
4 |
Correct |
26 ms |
21588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
21588 KB |
Output is correct |
2 |
Correct |
27 ms |
21580 KB |
Output is correct |
3 |
Correct |
27 ms |
21536 KB |
Output is correct |
4 |
Correct |
26 ms |
21588 KB |
Output is correct |
5 |
Correct |
14 ms |
21588 KB |
Output is correct |
6 |
Correct |
15 ms |
21588 KB |
Output is correct |
7 |
Correct |
16 ms |
21588 KB |
Output is correct |
8 |
Correct |
14 ms |
21524 KB |
Output is correct |
9 |
Correct |
13 ms |
21552 KB |
Output is correct |
10 |
Correct |
13 ms |
21588 KB |
Output is correct |
11 |
Correct |
13 ms |
21552 KB |
Output is correct |
12 |
Correct |
14 ms |
21588 KB |
Output is correct |
13 |
Correct |
14 ms |
21520 KB |
Output is correct |
14 |
Correct |
13 ms |
21588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
356 ms |
38592 KB |
Output is correct |
2 |
Correct |
369 ms |
36800 KB |
Output is correct |
3 |
Correct |
374 ms |
35816 KB |
Output is correct |
4 |
Correct |
381 ms |
37716 KB |
Output is correct |
5 |
Correct |
368 ms |
37736 KB |
Output is correct |
6 |
Correct |
393 ms |
39196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
21588 KB |
Output is correct |
2 |
Correct |
27 ms |
21580 KB |
Output is correct |
3 |
Correct |
27 ms |
21536 KB |
Output is correct |
4 |
Correct |
26 ms |
21588 KB |
Output is correct |
5 |
Correct |
14 ms |
21588 KB |
Output is correct |
6 |
Correct |
15 ms |
21588 KB |
Output is correct |
7 |
Correct |
16 ms |
21588 KB |
Output is correct |
8 |
Correct |
14 ms |
21524 KB |
Output is correct |
9 |
Correct |
13 ms |
21552 KB |
Output is correct |
10 |
Correct |
13 ms |
21588 KB |
Output is correct |
11 |
Correct |
13 ms |
21552 KB |
Output is correct |
12 |
Correct |
14 ms |
21588 KB |
Output is correct |
13 |
Correct |
14 ms |
21520 KB |
Output is correct |
14 |
Correct |
13 ms |
21588 KB |
Output is correct |
15 |
Correct |
356 ms |
38592 KB |
Output is correct |
16 |
Correct |
369 ms |
36800 KB |
Output is correct |
17 |
Correct |
374 ms |
35816 KB |
Output is correct |
18 |
Correct |
381 ms |
37716 KB |
Output is correct |
19 |
Correct |
368 ms |
37736 KB |
Output is correct |
20 |
Correct |
393 ms |
39196 KB |
Output is correct |
21 |
Correct |
329 ms |
38080 KB |
Output is correct |
22 |
Correct |
342 ms |
36276 KB |
Output is correct |
23 |
Correct |
347 ms |
35384 KB |
Output is correct |
24 |
Correct |
365 ms |
37544 KB |
Output is correct |
25 |
Correct |
363 ms |
40244 KB |
Output is correct |
26 |
Correct |
332 ms |
38072 KB |
Output is correct |
27 |
Correct |
332 ms |
36244 KB |
Output is correct |
28 |
Correct |
353 ms |
35356 KB |
Output is correct |
29 |
Correct |
360 ms |
36768 KB |
Output is correct |
30 |
Correct |
379 ms |
37812 KB |
Output is correct |
31 |
Correct |
333 ms |
38232 KB |
Output is correct |
32 |
Correct |
393 ms |
36260 KB |
Output is correct |
33 |
Correct |
351 ms |
35524 KB |
Output is correct |
34 |
Correct |
371 ms |
37312 KB |
Output is correct |
35 |
Correct |
361 ms |
40068 KB |
Output is correct |
36 |
Correct |
344 ms |
38380 KB |
Output is correct |