| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 125829 | mechfrog88 | Valley (BOI19_valley) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
struct node{
ll point;
ll index;
ll weight;
};
struct ed{
ll u,v,w;
};
vector <vector<node>> graph;
vector <ll> euler;
vector <pair<ll,ll>> pos;
vector <ed> edge;
vector <ll> index;
void dfs(ll p, ll v){
pos[v].first = euler.size();
index[v] = euler.size();
euler.push_back(v);
for (int z=0;z<graph[v].size();z++){
if (graph[v][z].point == p) continue;
dfs(v,graph[v][z].point);
euler.push_back(v);
}
pos[v].second = euler.size()-1;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,s,q,e;
cin >> n >> s >> q >> e;
graph.resize(n+1);
for (int z=0;z<n-1;z++){
node temp;
ll a,b;
cin >> a >> b >> temp.weight;
temp.index = z+1;
temp.point = b;
graph[a].push_back(temp);
temp.point = a;
graph[b].push_back(temp);
ed ede;
ede.u = a; ede.v = b; ede.w = temp.weight;
edge.push_back(ede);
}
vector <bool> shops(n+1,false);
for (int z=0;z<s;z++){
ll temp;
cin >> temp;
shops[temp] = true;
}
pos.resize(n+1);
index.resize(n+1);
dfs(0,1);
if (s == n){
for (int z=0;z<q;z++){
ll k,t;
cin >> k >> t;
k--;
ll l,r;
ll s1 = pos[edge[k].u].second-pos[edge[k].u].first;
ll s2 = pos[edge[k].v].second-pos[edge[k].v].first;
if (s1 > s2){
l = pos[edge[k].v].first;
r = pos[edge[k].v].second;
}
else{
l = pos[edge[k].u].first;
r = pos[edge[k].u].second;
}
bool in1 = false;
bool in2 = false;
if (l <= index[t] && index[t] <= r){
in1 = true;
}
if (l <= index[e] && index[e] <= r){
in2 = true;
}
if (in1 ^ in2){
cout << 0 << endl;
} else {
cout << "escaped" << endl;
}
}
return 0;
}
for (int z=0;z<q;z++){
ll r,t;
cin >> r >> t;
vector <ll> distance(n+1,LLONG_MAX);
queue <node> que;
vector <bool> visited(n+1,false);
visited[t] = true;
distance[t] = 0;
for (int x=0;x<graph[t].size();x++){
if (graph[t][x].index == r) continue;
if (visited[graph[t][x].point]) continue;
distance[graph[t][x].point] = graph[t][x].weight;
que.push(graph[t][x]);
}
while (!que.empty()){
node temp = que.front();
ll v = temp.point;
visited[v] = true;
que.pop();
for (int x=0;x<graph[v].size();x++){
if (graph[v][x].index == r) continue;
if (visited[graph[v][x].point]) continue;
distance[graph[v][x].point] = distance[v]+graph[v][x].weight;
que.push(graph[v][x]);
}
}
if (visited[e] == true){
cout << "escaped" << endl;
}
else {
ll mini = LLONG_MAX;
for (int z=1;z<=n;z++){
if (shops[z])
mini = min(distance[z],mini);
}
if (mini == LLONG_MAX){
cout << "oo" << endl;
} else {
cout << mini << endl;
}
}
}
}