# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
254954 |
2020-07-30T22:18:29 Z |
jovan_b |
Valley (BOI19_valley) |
C++17 |
|
346 ms |
29768 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll res[100005];
vector <pair <int, int>> graf[100005];
ll depth[100005];
pair <ll, int> niz[100005];
int e;
const ll INF = 1000000000000000LL;
struct segment{
ll lazy, res;
} seg[400005];
int tajm;
int in[100005];
int out[100005];
bool jeste[100005];
vector <pair <int, int>> kv[100005];
int n;
void init(int node, int l, int r){
if(l == r){
if(niz[l].second == 1) seg[node].res = niz[l].first;
else seg[node].res = INF;
return;
}
int mid = (l+r)/2;
init(node*2, l, mid);
init(node*2+1, mid+1, r);
seg[node].res = min(seg[node*2].res, seg[node*2+1].res);
}
void dfs1(int v, int parent, int kolko){
depth[v] = depth[parent] + kolko;
in[v] = ++tajm;
niz[in[v]] = {depth[v], jeste[v]};
for(auto c : graf[v]){
if(c.first == parent) continue;
dfs1(c.first, v, c.second);
}
out[v] = tajm;
}
void propagate(int node, int l, int r){
seg[node].res += seg[node].lazy;
if(l == r){
seg[node].lazy = 0;
return;
}
seg[node*2].lazy += seg[node].lazy;
seg[node*2+1].lazy += seg[node].lazy;
seg[node].lazy = 0;
}
void upd(int node, int l, int r, int tl, int tr, int val){
if(tl > tr) return;
propagate(node, l, r);
if(tl > r || l > tr) return;
if(tl <= l && r <= tr){
seg[node].lazy += val;
propagate(node, l, r);
return;
}
int mid = (l+r)/2;
upd(node*2, l, mid, tl, tr, val);
upd(node*2+1, mid+1, r, tl, tr, val);
seg[node].res = min(seg[node*2].res, seg[node*2+1].res);
}
ll query(int node, int l, int r, int tl, int tr){
if(tl > tr) return INF;
propagate(node, l, r);
if(tl > r || l > tr) return INF;
if(tl <= l && r <= tr) return seg[node].res;
int mid = (l+r)/2;
return min(query(node*2, l, mid, tl, tr), query(node*2+1, mid+1, r, tl, tr));
}
struct edge{
int a, b, c;
} grana[100005];
bool is_parent(int a, int b){
return in[a] <= in[b] && out[b] <= out[a];
}
void dfs(int v, int parent, int kolko){
upd(1, 1, n, 1, n, kolko);
upd(1, 1, n, in[v], out[v], -2*kolko);
for(auto c : kv[v]){
int edg = c.first;
if(in[grana[edg].a] > in[grana[edg].b]) swap(grana[edg].a, grana[edg].b);
int b = grana[edg].b;
if(is_parent(b, v)) res[c.second] = query(1, 1, n, in[b], out[b]);
else res[c.second] = min(query(1, 1, n, 1, in[b]-1), query(1, 1, n, out[b]+1, n));
}
for(auto c : graf[v]){
if(c.first == parent) continue;
dfs(c.first, v, c.second);
}
upd(1, 1, n, 1, n, -kolko);
upd(1, 1, n, in[v], out[v], 2*kolko);
}
bool check(int x, int edg){
if(in[grana[edg].a] > in[grana[edg].b]) swap(grana[edg].a, grana[edg].b);
int b = grana[edg].b;
if(is_parent(b, e)) return is_parent(b, x);
else return !is_parent(b, x);
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int s, q;
cin >> n >> s >> q >> e;
for(int i=1; i<n; i++){
int a, b, c;
cin >> a >> b >> c;
graf[a].push_back({b, c});
graf[b].push_back({a, c});
grana[i] = {a, b, c};
}
for(int j=1; j<=s; j++){
int x;
cin >> x;
jeste[x] = 1;
}
dfs1(1, 0, 0);
init(1, 1, n);
for(int j=1; j<=q; j++){
int a, b;
cin >> b >> a;
if(check(a, b)){
res[j] = -1;
continue;
}
res[j] = INF;
kv[a].push_back({b, j});
}
dfs(1, 0, 0);
for(int j=1; j<=q; j++){
if(res[j] == -1) cout << "escaped\n";
else if(res[j] > INF/10) cout << "oo\n";
else cout << res[j] << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5248 KB |
Output is correct |
2 |
Correct |
8 ms |
5248 KB |
Output is correct |
3 |
Correct |
7 ms |
5352 KB |
Output is correct |
4 |
Correct |
7 ms |
5372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5248 KB |
Output is correct |
2 |
Correct |
8 ms |
5248 KB |
Output is correct |
3 |
Correct |
7 ms |
5352 KB |
Output is correct |
4 |
Correct |
7 ms |
5372 KB |
Output is correct |
5 |
Correct |
5 ms |
5248 KB |
Output is correct |
6 |
Correct |
7 ms |
5248 KB |
Output is correct |
7 |
Correct |
5 ms |
5248 KB |
Output is correct |
8 |
Correct |
5 ms |
5248 KB |
Output is correct |
9 |
Correct |
5 ms |
5288 KB |
Output is correct |
10 |
Correct |
5 ms |
5296 KB |
Output is correct |
11 |
Correct |
5 ms |
5248 KB |
Output is correct |
12 |
Correct |
7 ms |
5248 KB |
Output is correct |
13 |
Correct |
5 ms |
5248 KB |
Output is correct |
14 |
Correct |
5 ms |
5248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
237 ms |
20216 KB |
Output is correct |
2 |
Correct |
323 ms |
23672 KB |
Output is correct |
3 |
Correct |
272 ms |
23696 KB |
Output is correct |
4 |
Correct |
299 ms |
25772 KB |
Output is correct |
5 |
Correct |
255 ms |
24504 KB |
Output is correct |
6 |
Correct |
300 ms |
29768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5248 KB |
Output is correct |
2 |
Correct |
8 ms |
5248 KB |
Output is correct |
3 |
Correct |
7 ms |
5352 KB |
Output is correct |
4 |
Correct |
7 ms |
5372 KB |
Output is correct |
5 |
Correct |
5 ms |
5248 KB |
Output is correct |
6 |
Correct |
7 ms |
5248 KB |
Output is correct |
7 |
Correct |
5 ms |
5248 KB |
Output is correct |
8 |
Correct |
5 ms |
5248 KB |
Output is correct |
9 |
Correct |
5 ms |
5288 KB |
Output is correct |
10 |
Correct |
5 ms |
5296 KB |
Output is correct |
11 |
Correct |
5 ms |
5248 KB |
Output is correct |
12 |
Correct |
7 ms |
5248 KB |
Output is correct |
13 |
Correct |
5 ms |
5248 KB |
Output is correct |
14 |
Correct |
5 ms |
5248 KB |
Output is correct |
15 |
Correct |
237 ms |
20216 KB |
Output is correct |
16 |
Correct |
323 ms |
23672 KB |
Output is correct |
17 |
Correct |
272 ms |
23696 KB |
Output is correct |
18 |
Correct |
299 ms |
25772 KB |
Output is correct |
19 |
Correct |
255 ms |
24504 KB |
Output is correct |
20 |
Correct |
300 ms |
29768 KB |
Output is correct |
21 |
Correct |
224 ms |
23416 KB |
Output is correct |
22 |
Correct |
269 ms |
23016 KB |
Output is correct |
23 |
Correct |
276 ms |
22904 KB |
Output is correct |
24 |
Correct |
285 ms |
24440 KB |
Output is correct |
25 |
Correct |
279 ms |
27828 KB |
Output is correct |
26 |
Correct |
228 ms |
23548 KB |
Output is correct |
27 |
Correct |
232 ms |
23096 KB |
Output is correct |
28 |
Correct |
243 ms |
23064 KB |
Output is correct |
29 |
Correct |
268 ms |
25208 KB |
Output is correct |
30 |
Correct |
346 ms |
26800 KB |
Output is correct |
31 |
Correct |
245 ms |
23520 KB |
Output is correct |
32 |
Correct |
256 ms |
23160 KB |
Output is correct |
33 |
Correct |
280 ms |
23124 KB |
Output is correct |
34 |
Correct |
333 ms |
24876 KB |
Output is correct |
35 |
Correct |
271 ms |
27148 KB |
Output is correct |
36 |
Correct |
260 ms |
24824 KB |
Output is correct |