#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll dp[maxN],in[maxN],out[maxN],tg=0;
bool c[maxN];
ll P[maxN][18];
const ll inf2=1e18;
struct qq
{
ll fi,se,id;
};
vector<qq>g[maxN];
ll h[maxN],d[maxN];
ll val[maxN];
ll pos[maxN];
void cc(ll u,ll p)
{
P[u][0]=p;
for(int i=1;i<=17;i++) P[u][i]=P[P[u][i-1]][i-1];
for(auto vv:g[u])
{
if(vv.fi!=p)
{
cc(vv.fi,u);
}
}
}
void dfs(ll u,ll p)
{
dp[u]=inf;
if(c[u]==1) dp[u]=0;
in[u]=++tg;
vector<pli>cc;
for(auto vv:g[u])
{
if(vv.fi!=p)
{
pos[vv.id]=vv.fi;
h[vv.fi]=h[u]+1;
d[vv.fi]=d[u]+vv.se;
dfs(vv.fi,u);
dp[u]=min(dp[u],dp[vv.fi]+vv.se);
cc.pb({dp[vv.fi]+vv.se,vv.fi});
}
}
sort(cc.begin(),cc.end());
if(c[u]==1)
{
for(auto vv:g[u])
{
if(vv.fi!=p)
{
val[vv.fi]=-d[u];
}
}
}
else
{
for(int i=0;i<min(2,(int)cc.size());i++)
{
for(auto vv:g[u])
{
if(vv.fi!=p&&vv.fi!=cc[i].se)
{
val[vv.fi]=min(val[vv.fi],-d[u]+cc[i].fi);
}
}
}
}
out[u]=tg;
}
ll mn[maxN][18];
void dfs2(ll u,ll p)
{
mn[u][0]=val[u];
for(int i=1;i<=17;i++) mn[u][i]=min(mn[u][i-1],mn[P[u][i-1]][i-1]);
for(auto vv:g[u])
{
if(vv.fi!=p)
{
dfs2(vv.fi,u);
}
}
}
ll get(ll u,ll p)
{
ll d=h[u]-h[p];
ll ans=inf;
for(int i=17;i>=0;i--)
{
if(d>>i&1)
{
ans=min(ans,mn[u][i]);
u=P[u][i];
}
}
return ans;
}
ll n,q,s,e;
bool ipar(ll u,ll p)
{
return (in[p]<=in[u]&&out[u]<=out[p]);
}
void solve()
{
cin >> n >> s >> q >> e;
for(int i=1;i<n;i++)
{
ll u,v,w;
cin >> u >> v >> w;
g[u].pb({v,w,i});
g[v].pb({u,w,i});
}
for(int i=1;i<=n;i++) val[i]=inf,c[i]=0;
for(int i=1;i<=s;i++)
{
ll u;
cin >> u;
c[u]=1;
}
cc(e,e);
dfs(e,e);
dfs2(e,e);
while(q--)
{
ll id,u;
cin >> id >> u;
ll v=pos[id];
if(ipar(u,v))
{
ll ans=inf;
ans=min(ans,dp[u]);
ans=min(ans,get(u,v)+d[u]);
if(ans>=inf2) cout <<"oo\n";
else cout << ans<<'\n';
}
else
{
cout <<"escaped\n";
}
}
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5076 KB |
Output is correct |
2 |
Correct |
4 ms |
5204 KB |
Output is correct |
3 |
Correct |
5 ms |
5172 KB |
Output is correct |
4 |
Correct |
4 ms |
5204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5076 KB |
Output is correct |
2 |
Correct |
4 ms |
5204 KB |
Output is correct |
3 |
Correct |
5 ms |
5172 KB |
Output is correct |
4 |
Correct |
4 ms |
5204 KB |
Output is correct |
5 |
Correct |
4 ms |
5428 KB |
Output is correct |
6 |
Correct |
3 ms |
5416 KB |
Output is correct |
7 |
Correct |
4 ms |
5460 KB |
Output is correct |
8 |
Correct |
4 ms |
5460 KB |
Output is correct |
9 |
Correct |
4 ms |
5424 KB |
Output is correct |
10 |
Correct |
4 ms |
5436 KB |
Output is correct |
11 |
Correct |
4 ms |
5460 KB |
Output is correct |
12 |
Correct |
4 ms |
5460 KB |
Output is correct |
13 |
Correct |
4 ms |
5460 KB |
Output is correct |
14 |
Correct |
4 ms |
5460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
153 ms |
45808 KB |
Output is correct |
2 |
Correct |
174 ms |
45860 KB |
Output is correct |
3 |
Correct |
194 ms |
46156 KB |
Output is correct |
4 |
Correct |
229 ms |
49548 KB |
Output is correct |
5 |
Correct |
203 ms |
49452 KB |
Output is correct |
6 |
Correct |
228 ms |
53452 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5076 KB |
Output is correct |
2 |
Correct |
4 ms |
5204 KB |
Output is correct |
3 |
Correct |
5 ms |
5172 KB |
Output is correct |
4 |
Correct |
4 ms |
5204 KB |
Output is correct |
5 |
Correct |
4 ms |
5428 KB |
Output is correct |
6 |
Correct |
3 ms |
5416 KB |
Output is correct |
7 |
Correct |
4 ms |
5460 KB |
Output is correct |
8 |
Correct |
4 ms |
5460 KB |
Output is correct |
9 |
Correct |
4 ms |
5424 KB |
Output is correct |
10 |
Correct |
4 ms |
5436 KB |
Output is correct |
11 |
Correct |
4 ms |
5460 KB |
Output is correct |
12 |
Correct |
4 ms |
5460 KB |
Output is correct |
13 |
Correct |
4 ms |
5460 KB |
Output is correct |
14 |
Correct |
4 ms |
5460 KB |
Output is correct |
15 |
Correct |
153 ms |
45808 KB |
Output is correct |
16 |
Correct |
174 ms |
45860 KB |
Output is correct |
17 |
Correct |
194 ms |
46156 KB |
Output is correct |
18 |
Correct |
229 ms |
49548 KB |
Output is correct |
19 |
Correct |
203 ms |
49452 KB |
Output is correct |
20 |
Correct |
228 ms |
53452 KB |
Output is correct |
21 |
Correct |
160 ms |
49108 KB |
Output is correct |
22 |
Correct |
192 ms |
49124 KB |
Output is correct |
23 |
Correct |
191 ms |
49456 KB |
Output is correct |
24 |
Correct |
225 ms |
53252 KB |
Output is correct |
25 |
Correct |
218 ms |
58316 KB |
Output is correct |
26 |
Correct |
148 ms |
49172 KB |
Output is correct |
27 |
Correct |
180 ms |
49148 KB |
Output is correct |
28 |
Correct |
198 ms |
49388 KB |
Output is correct |
29 |
Correct |
216 ms |
51936 KB |
Output is correct |
30 |
Correct |
242 ms |
54604 KB |
Output is correct |
31 |
Correct |
172 ms |
49160 KB |
Output is correct |
32 |
Correct |
187 ms |
49256 KB |
Output is correct |
33 |
Correct |
203 ms |
49632 KB |
Output is correct |
34 |
Correct |
217 ms |
52944 KB |
Output is correct |
35 |
Correct |
225 ms |
58032 KB |
Output is correct |
36 |
Correct |
199 ms |
53196 KB |
Output is correct |