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>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using ll = long long;
const ll MAXN = 1e6 + 5;
const ll INF = 1e16;
const ll LOG = 30;
#define pll pair <ll, ll>
#define vll vector <ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " " << (x) << endl;
#define lc (pos<<1)
#define rc ((pos<<1)+1)
#define mid ((l+r)>>1)
ll n, s, q, e;
vector <vector <pll> > adj (MAXN);
array <ll, 3> edg [MAXN];
bool b [MAXN];
ll dep [MAXN], dis [MAXN], val [MAXN];
ll anc [MAXN][LOG], spa [MAXN][LOG];
vll lis;
void dfs(ll x, ll px){
anc[x][0] = px;
val[x] = INF;
if(b[x]) val[x] = dis[x];
for(auto nx : adj[x]){
ll y = nx.fi, w = nx.se;
if(y == px) continue;
dep[y] = dep[x] + 1;
dis[y] = dis[x] + w;
dfs(y, x);
val[x] = min(val[x], val[y]);
}
spa[x][0] = val[x] - (2*dis[x]);
if(val[x] == INF) spa[x][0] = INF;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> s >> q >> e;
for(ll i = 1; i <= n-1; i++){
ll u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
edg[i] = {u, v, w};
}
for(ll i = 1; i <= s; i++){
ll x; cin >> x; b[x] = 1;
}
dfs(e, 0);
for(ll j = 1; j < LOG; j++){
for(ll i = 1; i <= n; i++){
anc[i][j] = anc[anc[i][j-1]][j-1];
spa[i][j] = min(spa[i][j-1], spa[anc[i][j-1]][j-1]);
}
}
for(ll i = 1; i <= q; i++){
ll ed, x; cin >> ed >> x;
ll u = edg[ed][0], v = edg[ed][1];
if(dep[u] > dep[v]) swap(u, v);
if(dep[x] < dep[v]){
cout << "escaped" << endl;
continue;
}
ll fw = x, mn = spa[fw][0];
for(ll j = LOG-1; j >= 0; j--){
if(dep[anc[fw][j]] >= dep[v]){
mn = min(mn, spa[fw][j]);
fw = anc[fw][j];
mn = min(mn, spa[fw][0]);
}
}
if(fw != v){
cout << "escaped" << endl;
continue;
}
if(mn == INF) cout << "oo" << endl;
else cout << dis[x] + mn << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |