/*#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#pragma ("reroll") */
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define ins insert
#define F first
#define S second
const int mod = 1e7 + 7,N = 1100;
int d[N];
int up[N][20];
vector<pair<int,int>>g[N];
int d1[N];
bool was[N];
void dfs(int v,int p,int bl1,int bl2){
was[v] = 1;
up[v][0] = p;
for(int i = 1;i<20;i++) up[v][i] = up[up[v][i-1]][i-1];
for(auto xz : g[v]){
int to = xz.F;
int w = xz.S;
if(to==p || (bl1 == v && bl2 == to) || (bl2 == v && bl1 == to)) continue;
d[to] = d[v] + 1;
d1[to] = d1[v] + w;
dfs(to,v,bl1,bl2);
}
}
int lca(int a,int b){
if(d[a]>d[b]) swap(a,b);
int dist =d[b] - d[a];
for(int i = 0;i<20;i++){
if(dist & (1<<i)){
b = up[b][i];
}
}
if(a==b) return a;
for(int i = 19;i>=0;i--){
if(up[a][i]!=up[b][i]){
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
}
signed main(){
//freopen("justcoding.in","r",stdin);
//freopen("justcoding.out","w",stdout);
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,s,q,e;
cin >> n >> s >> q >> e;
int u1[n],v1[n];
for(int i = 1;i<n;i++){
int c;
cin >> u1[i] >> v1[i] >> c;
g[u1[i]].pb({v1[i],c});
g[v1[i]].pb({u1[i],c});
}
int a[s+1];
for(int i = 1;i<=s;i++){
cin >> a[i];
}
while(q--){
int l,r;
cin >> l >> r;
dfs(r,0,u1[l],v1[l]);
int mn = 1e18;
if(was[e]) cout << "escaped\n";
else{
for(int i = 1;i<=s;i++){
if(was[a[i]]){
int x = lca(a[i],r);
mn = min(mn,d1[r]-d1[x] + d1[a[i]]-d1[x]);
}
}
if(mn==INT_MAX) cout << "oo\n";
else cout << mn << '\n';
}
for(int i = 1;i<=n;i++){
was[i] = 0;
d[i] = 0;
d1[i] = 0;
for(int j = 0;j<20;j++) up[i][j] = 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... |