#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const long long INF = 2e18;
const int N = 1e5 + 4;
int n, s, q, ex, timer;
int h[N], tin[N], tout[N];
int isShop[N], par[18][N];
vector<pair<int, int>> adj[N];
pair<pair<int, int>, int> e[N];
long long dp[N], Min[18][N], dep[N];
void dfs(int u, int p) {
tin[u] = ++timer;
dp[u] = isShop[u] ? 0 : INF;
for (auto [v, w]: adj[u]) if (v != p) {
dep[v] = dep[u] + w;
h[v] = h[u] + 1;
par[0][v] = u;
dfs(v, u);
mini(dp[u], dp[v] + w);
}
tout[u] = timer;
for (int j = 1; j <= 17; j++) Min[j][u] = INF;
}
bool isAncestor(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
void pre_dfs(int u) {
if (dp[u] < INF) dp[u] -= dep[u];
for (auto [v, w]: adj[u]) if (v != par[0][u]) {
Min[0][v] = dp[u];
for (int j = 1; j <= 17; j++) {
par[j][v] = par[j - 1][par[j - 1][v]];
Min[j][v] = min(Min[j - 1][v], Min[j - 1][par[j - 1][v]]);
}
pre_dfs(v);
}
}
long long calc(int u, int p) {
int k = h[u] - h[p]; long long res = dp[u] - dep[u] * (!isShop[u]);
for (int j = 0; (1 << j) <= k; j++) if (k >> j & 1) {
res = min(res, Min[j][u]); u = par[j][u];
}
return res;
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp","r")) {
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n >> s >> q >> ex;
for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
e[i] = {{u, v}, w};
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for (int i = 1, x; i <= s; i++) {
cin >> x; isShop[x] = true;
}
dfs(ex, -1); pre_dfs(ex);
while (q--) {
int I, R; cin >> I >> R;
int u = e[I].fi.fi;
int v = e[I].fi.se;
if (tin[u] < tin[v]) swap(u, v);
if (!isAncestor(u, R)) cout << "escaped\n";
else {
long long ans = calc(R, u) + dep[R];
if (ans >= INF) cout << "oo\n";
else cout << ans << '\n';
}
}
}
Compilation message
valley.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
63 | main() {
| ^~~~
valley.cpp: In function 'int main()':
valley.cpp:68:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:69:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
36456 KB |
Output is correct |
| 2 |
Correct |
196 ms |
36060 KB |
Output is correct |
| 3 |
Correct |
179 ms |
36112 KB |
Output is correct |
| 4 |
Correct |
194 ms |
37832 KB |
Output is correct |
| 5 |
Correct |
183 ms |
38004 KB |
Output is correct |
| 6 |
Correct |
216 ms |
39808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
