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;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5, inf = 1e12;
int t,n,a[N], dp[N], dep[N],lv[N],tin,in[N],out[N], fix[N],m,q,rt,ed_a[N],ed_b[N];
vector <pii> v[N];
pii par[N][20];
void dfs(int a, int p) {
if (!fix[a]) dp[a] = inf;
else dp[a] = -lv[a];
dep[a] = dep[p] + 1;
tin++;
in[a] = tin;
for (pii sth : v[a]) {
int to = sth.f; int c = sth.s;
if (to == p) continue;
lv[to] = lv[a] + c;
dfs(to, a);
if (dp[to] != inf)
dp[a] = min(dp[a], dp[to] + 2 * (lv[to] - lv[a]));
}
out[a] = tin;
}
void dfs1(int a, int p) {
par[a][0] = {p, dp[a]};
for (int i = 1; i <= 18; i++) {
if (par[a][i - 1].f) {
par[a][i].f = par[par[a][i - 1].f][i - 1].f;
par[a][i].s = min(par[a][i - 1].s, par[par[a][i - 1].f][i - 1].s);
}
}
for (pii sth : v[a]) {
int to = sth.f; int c = sth.s;
if (to == p) continue;
dfs1(to, a);
}
}
int upper(int a, int b) {
return (in[a] <= in[b] && out[a] >= out[b]);
}
main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>q>>rt;
for (int i = 1; i <= n - 1; i++) {
int a, b, c; cin>>a>>b>>c;
ed_a[i] = a; ed_b[i] = b;
v[a].pb({b, c});
v[b].pb({a, c});
}
for (int i = 1; i <= m; i++) {
int a; cin>>a;
fix[a] = 1;
}
dfs(rt, 0);
dfs1(rt, 0);
for (int i = 1; i <= q; i++) {
int idx, vert, a, b;
cin>>idx>>vert;
a = ed_a[idx]; b = ed_b[idx];
if (lv[a] < lv[b]) swap(a, b);
if(!upper(a, vert)) {
cout<<"escaped\n"; continue;
}
int dif = dep[vert] - dep[a] + 1;
int ans = inf, cur = vert;
for (int i = 0; i <= 18; i++) {
if ((1<<i)&dif) {
ans = min(ans, par[cur][i].s);
cur = par[cur][i].f;
}
}
if (ans == inf) cout<<"oo\n";
else cout<<ans + lv[vert]<<"\n";
}
}
Compilation message (stderr)
valley.cpp: In function 'void dfs1(long long int, long long int)':
valley.cpp:40:29: warning: unused variable 'c' [-Wunused-variable]
40 | int to = sth.f; int c = sth.s;
| ^
valley.cpp: At global scope:
valley.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
48 | main() {
| ^~~~
# | 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... |