/**************************************************************
Submitted By: Mayuresh N. Patle
Written On: Wednesday, July 27, 2022
**************************************************************/
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define mod1 998244353
#define rep(i,s,e) for(i=s;i<e;++i)
#define repr(i,s,e) for(i=s;i>e;--i)
#define fp(i) fixed<<setprecision(i)
#define in(a) for(auto &ghe:a) cin>>ghe;
#define in2d(a) for(auto &ghe:a) for(auto &he:ghe) cin>>he;
#define out(a) for(auto &ghe:a) cout<<ghe<<" ";cout<<endl;
#define out2d(a) {for(auto &he:a) {out(he)}}
#define loop(i,a) for(auto &i:a)
#define inrange(i,j,k) (((i)<=(j)) && ((j)<(k)))
#define make(a,i) memset(a,i,sizeof(a))
#define chk(x) cerr<<(#x)<<":"<<(x)<<endl;
#define chk2(x,y) cerr<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<endl;
#define chk3(x,y,z) cerr<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector <ll> vll;
typedef vector <float> vf;
typedef vector <ld> vld;
#define pb push_back
#define pob() pop_back()
typedef pair <ll,ll> pll;
#define F first
#define S second
#define mp(a,b) make_pair(a,b)
typedef vector <pll> vp;
typedef vector <bool> flags;
#define all(v) begin(v),end(v)
#define amin(var, val) var = (val)<var ? (val) : var
#define amax(var, val) var = (val)>var ? (val) : var
class edge
{
public:
ll u,v,w;
edge (){}
edge (ll u, ll v, ll w): u(u), v(v), w(w){}
ll op(ll x) {return x^u^v;}
};
const ll N=1e5+1, h=18, oo=1e18;
vll G[N];
vector <edge> e;
ll up[N][h], dp[N][h], val[N];
ll dist[N], tin[N], tout[N], _t=0;
ll sd[N], s[N];
void dfs(ll v, ll p)
{
tin[v] = ++_t;
up[v][0] = p;
dist[v] += dist[p];
sd[v] = oo;
if(s[v]) sd[v] = dist[v];
loop(i, G[v])
{
ll u=e[i].op(v), w=e[i].w;
if(u==p) continue;
dist[u] = w;
dfs(u,v);
e[i].v = u;
e[i].u = v;
amin(sd[v], sd[u]);
}
dp[v][0] = oo;
if(sd[v]!=oo) dp[v][0] = sd[v] - 2ll*dist[v];
val[v] = dp[v][0];
tout[v] = ++_t;
}
bool is_anc(ll p, ll v)
{
return tin[p]<=tin[v] and tout[p]>=tout[v];
}
ll get(ll v,ll p)
{
ll i, ans=val[p];
rep(i,0,h)
{
if(is_anc(p, up[v][i])) amin(ans, dp[v][i]), v=up[v][i];
}
return ans;
}
void preprocess()
{
return;
}
void solve()
{
ll n,m,q,r,i;
cin>>n>>m>>q>>r;
rep(i,1,n)
{
ll u,v,w;
cin>>u>>v>>w;
G[u].pb(e.size());
G[v].pb(e.size());
e.pb(edge(u,v,w));
}
while(m--) cin>>i, s[i]=1;
loop(v, dp) loop(i, v) i=oo;
dfs(r, 0);
rep(i,1,h) rep(r,1,n+1)
{
dp[r][i] = min(dp[r][i-1], dp[up[r][i-1]][i-1]);
up[r][i] = up[up[r][i-1]][i-1];
}
while(q--)
{
cin>>i>>r;
--i;
ll v = e[i].v;
if(!is_anc(v, r)) cout<<"escaped\n";
else
{
ll ans = get(r, v);
if(ans==oo) cout<<"oo\n";
else cout<<ans+dist[r]<<"\n";
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll T=1,i;
//cin>>T;
preprocess();
rep(i,0,T)
{
//cout<<"Case #"<<i+1<<": ";
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
16864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
16864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
148 ms |
42360 KB |
Output is correct |
| 2 |
Correct |
211 ms |
45088 KB |
Output is correct |
| 3 |
Correct |
186 ms |
45000 KB |
Output is correct |
| 4 |
Correct |
190 ms |
46784 KB |
Output is correct |
| 5 |
Correct |
188 ms |
46892 KB |
Output is correct |
| 6 |
Correct |
209 ms |
48816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
16864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
