| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 603803 |
2022-07-24T11:55:57 Z |
LunaMeme |
Valley (BOI19_valley) |
C++14 |
|
2 ms |
2004 KB |
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int , int > ii;
typedef vector<ii> vii;
#define MP make_pair
#define PB push_back
#define FOR(i, x, y) for(int i = x; i < y; i ++)
const int MAXN = 1e3 + 5;
ii segtree[4*MAXN]; //segtree on levels
vi tour;
vii arr;
int n,s , q, e;
vii adj[MAXN];
int indx = -1;
vii subtree(MAXN, {-1, -1});
ll dist[MAXN]; // distance from root
ii level[MAXN];
void dfs(int curr, int par){
indx ++;
tour.PB(curr);
if (subtree[curr].first == -1){
subtree[curr].first = indx;
}
subtree[curr].second = indx;
for (auto pr : adj[curr]){
int next = pr.first;
ll w = pr.second;
if (next == par) continue;
dist[next] = dist[curr] + w;
level[next] = MP(level[curr].first + 1, next);
dfs(next, curr);
indx ++;
tour.PB(curr);
subtree[curr].second = indx;
}
}
int pow_2 = 1;
void update(int i, ii val);
ii query(int l, int r);
int lca(int a , int b);
ll dist_in(int a,int b);
bool can_go(int a, int b, int des);
int shops[MAXN];
int main(){
cin >> n >> s >> q >> e;
vii edges(n - 1);
FOR(i, 0, n- 1){
int a, b, w; cin >>a >> b >> w;
adj[a].PB(MP(b, w));
adj[b].PB(MP(a, w));
edges[i] = MP(a,b);
}
//root at e
dist[e] = 0;
level[e] = MP(0, e);
dfs(e, -1);
while(pow_2 < (int)tour.size()){
pow_2 *= 2;
}
FOR(i, 0, 4*MAXN) segtree[i] = {1e9, 1e9};
for(auto i : tour){
//cout << i << " " << level[i].first << " " << level[i].second << '\n';
arr.PB(level[i]);
}
int j = 0;
for(auto pr : arr){
update(j, pr);
j++;
//cout << pr.first << ' '<< pr.second << '\n';
}
//FOR(i, 1, 2 * tour.size() + 1) cout << segtree[i].first << ',' << segtree[i].second << " ";
FOR(i, 0, s) cin >> shops[i];
FOR(k, 0, q){
int i , r; cin >> i >> r;
ii pr = edges[i - 1];
int dest;
if (dist[pr.first] < dist[pr.second])
dest = pr.second;
else dest = pr.first;
//check if r in dest subtree or not
if (subtree[r].first < subtree[dest].first || subtree[r].second > subtree[dest].second){
//cout << r << ' ' << dest << '\n';
cout << "escaped\n";
continue;
}
ll mn_dist = 1e18;
FOR(t, 0, s){
//cout << dist_in(shops[t], r) << '\n';
if (can_go(r, shops[t], dest)){
mn_dist = min(mn_dist, dist_in(shops[t], r));
}
}
if (mn_dist == 1e18) cout << "oo\n";
else cout << mn_dist << '\n';
}
}
void update(int i, ii val){
i += pow_2;
segtree[i] = val;
//cout << i << " VALUE : " << val.first << ' ' << val.second << '\n';
while(i /= 2){
segtree[i] = min(segtree[2*i], segtree[2*i + 1]);
}
}
ii query(int l, int r){
l += pow_2; r += pow_2;
if (r <l) swap(l ,r);
ii ans =MP(1e9, 0);
while(r > l && l > 0){
//cout << "LEFT : " << l << " RIGHT : " << r << '\n';
if (l % 2 == 1){
//cout << segtree[l].first << ' '<< segtree[l].second << '\n';
ans = min(ans, segtree[l]);
l ++;
}
if (r % 2 == 0){
ans = min(ans, segtree[r]);
r --;
}
l/= 2; r /=2;
//cout <<"ANSWER: " << ans.first << ' ' << ans.second << '\n';
}
if (l)
ans = min(ans, segtree[l]);
return ans;
}
int lca(int a , int b){
int l = subtree[a].second;
int r = subtree[b].second;
int l1 = subtree[a].first;
int r1 = subtree[b].first;
//cout << a << ' ' << b << ' ' << l << ' ' << r << '\n';
assert(query(l, r).second == query(l1, r1).second);
return query(l, r).second;
}
ll dist_in(int a,int b){
//cout << a << ' ' << b << ' ' << lca(a, b) << '\n';
//cout << dist[a] << ' ' << dist[b] << ' ' << dist[lca(a, b)] << '\n';
return dist[a] + dist[b] - 2*dist[lca(a,b)];
}
bool can_go(int a, int b, int dest){
return (((subtree[a].first < subtree[dest].first || subtree[a].second > subtree[dest].second) && (subtree[b].first < subtree[dest].first || subtree[b].second > subtree[dest].second)) ||((subtree[a].first >= subtree[dest].first && subtree[a].second <= subtree[dest].second) && subtree[b].first >= subtree[dest].first && subtree[b].second <= subtree[dest].second));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2004 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
