This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//çalışan kazanır//
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define pb push_back
#define S second
#define F first
#define all(x) x.begin(),x.end()
#define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0)
int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}}
const int N = 4e5 + 15;
const int INF = 1e18;
const int MOD = 1e9 + 7;
const int MODD = 1070234587ll;
const double eps = 0.0001;
const int p = 87;
int n, dst[N], tin[N], tout[N], q, s, t, e;
pair <int, int> reb[N];
vector <pair <int, int>> g[N];
void dfs (int v, int p) {
tin[v] = ++t;
for (auto to: g[v]) {
if (to.F == p) continue;
dfs (to.F, v);
dst[v] = min (dst[v], (int)(dst[to.F] + to.S));
}
tout[v] = t;
return;
}
void solution () {
cin >> n >> s >> q >> e;
for (int i = 1; i < n; ++ i) {
int v, u, w;
cin >> v >> u >> w;
g[v].pb ({u, w});
g[u].pb ({v, w});
reb[i] = {v, u};
}
for (int i = 1; i <= n; ++ i) dst[i] = INF;
for (int i = 1; i <= s; ++ i) {
int x; cin >> x;
dst[x] = 0;
}
dfs (e, 0);
while (q --) {
int v, idx;
cin >> v >> idx;
swap (v, idx);
int u = reb[idx].F, ans = INF;
if (tin[u] < tin[reb[idx].S]) u = reb[idx].S;
if (tin[u] <= tin[v] && tout[v] <= tout[u]) {
ans = dst[v];
ans = min (ans, dst[u] + (tin[v] - tin[u]));
if (ans == INF) cout << "oo\n";
else cout << ans << '\n';
} else cout << "escaped\n";
}
return;
}
signed main() {
// YOSIK();
// srand (time(0));
// freopen ("E.in", "r", stdin);
// freopen ("E.out", "w", stdout);
int TT = 1;// cin >> TT;
for (int i = 1; i <= TT; ++ i) {
// cout << "Case " << i << ": ";
solution ();
}
return 0;
}
# | 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... |