#include <bits/stdc++.h>
#define MAX 105000
using ll = long long;
typedef std::pair<ll,ll> pii;
std::vector<pii> con[MAX];
ll lift[MAX][20],prof[MAX],dist[MAX],plift[MAX][20],valr[MAX];
bool shops[MAX];
ll inf = 1LL<<60LL;
ll dfs(ll pos,ll prev,ll depth,ll d){
prof[pos]=depth;
dist[pos]=d;
lift[pos][0]=prev;
for(int i=1;i!=20;++i){
lift[pos][i]=lift[lift[pos][i-1]][i-1];
}
ll min = inf;
if(shops[pos])min=dist[pos];
for(auto&x:con[pos]){
if(x.first==prev)continue;
min=std::min(min,dfs(x.first,pos,depth+1,d+x.second));
}
valr[pos]=min-(2LL*dist[pos]);
return min;
}
void dfs2(int pos,int prev){
plift[pos][0]=std::min(valr[pos],valr[lift[pos][0]]);
for(int i=1;i!=20;++i){
plift[pos][i]=std::min(plift[pos][i-1],plift[lift[pos][i-1]][i-1]);
}
for(auto&x:con[pos]){
if(x.first==prev)continue;
dfs2(x.first,pos);
}
}
pii climb(int pos,int b){
ll min=valr[pos];
for(int i=19;i!=-1;--i){
if(b&(1<<i)){
min=std::min(min,plift[pos][i]);
pos=lift[pos][i];
}
}
return {pos,min};
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int N,S,Q,E;
std::cin>>N>>S>>Q>>E;--E;
std::vector<pii> conlis;
for(int i=1;i!=N;++i){
int a,b,c;
std::cin>>a>>b>>c;
--a;--b;
con[a].push_back({b,c});
con[b].push_back({a,c});
conlis.push_back({a,b});
}
for(int i=0;i!=S;++i){
int x;
std::cin>>x;
--x;
shops[x]=1;
}
dfs(E,E,0,0);
dfs2(E,E);
for(int i=0;i!=Q;++i){
int a,b;
std::cin>>a>>b;
--a;--b;
pii bloq = conlis[a];
int peq = bloq.first;
if(prof[bloq.second]>=prof[bloq.first])peq=bloq.second;
if(prof[peq]>prof[b]){
std::cout<<"escaped\n";
continue;
}
int dif = prof[b]-prof[peq];
auto res = climb(b,dif);
if(res.first!=peq){
std::cout<<"escaped\n";
continue;
}
ll ans = res.second+dist[b];
if(ans<(1LL<<50LL)){
std::cout<<ans<<"\n";
}else
std::cout<<"oo\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2900 KB |
Output is correct |
2 |
Correct |
4 ms |
2900 KB |
Output is correct |
3 |
Correct |
4 ms |
2948 KB |
Output is correct |
4 |
Correct |
4 ms |
2932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2900 KB |
Output is correct |
2 |
Correct |
4 ms |
2900 KB |
Output is correct |
3 |
Correct |
4 ms |
2948 KB |
Output is correct |
4 |
Correct |
4 ms |
2932 KB |
Output is correct |
5 |
Correct |
3 ms |
3240 KB |
Output is correct |
6 |
Correct |
3 ms |
3236 KB |
Output is correct |
7 |
Correct |
3 ms |
3236 KB |
Output is correct |
8 |
Correct |
3 ms |
3156 KB |
Output is correct |
9 |
Correct |
3 ms |
3188 KB |
Output is correct |
10 |
Correct |
3 ms |
3156 KB |
Output is correct |
11 |
Correct |
4 ms |
3156 KB |
Output is correct |
12 |
Correct |
3 ms |
3156 KB |
Output is correct |
13 |
Correct |
3 ms |
3156 KB |
Output is correct |
14 |
Correct |
3 ms |
3188 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
157 ms |
43900 KB |
Output is correct |
2 |
Correct |
184 ms |
47580 KB |
Output is correct |
3 |
Correct |
223 ms |
47828 KB |
Output is correct |
4 |
Correct |
246 ms |
49624 KB |
Output is correct |
5 |
Correct |
216 ms |
49740 KB |
Output is correct |
6 |
Correct |
270 ms |
51896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2900 KB |
Output is correct |
2 |
Correct |
4 ms |
2900 KB |
Output is correct |
3 |
Correct |
4 ms |
2948 KB |
Output is correct |
4 |
Correct |
4 ms |
2932 KB |
Output is correct |
5 |
Correct |
3 ms |
3240 KB |
Output is correct |
6 |
Correct |
3 ms |
3236 KB |
Output is correct |
7 |
Correct |
3 ms |
3236 KB |
Output is correct |
8 |
Correct |
3 ms |
3156 KB |
Output is correct |
9 |
Correct |
3 ms |
3188 KB |
Output is correct |
10 |
Correct |
3 ms |
3156 KB |
Output is correct |
11 |
Correct |
4 ms |
3156 KB |
Output is correct |
12 |
Correct |
3 ms |
3156 KB |
Output is correct |
13 |
Correct |
3 ms |
3156 KB |
Output is correct |
14 |
Correct |
3 ms |
3188 KB |
Output is correct |
15 |
Correct |
157 ms |
43900 KB |
Output is correct |
16 |
Correct |
184 ms |
47580 KB |
Output is correct |
17 |
Correct |
223 ms |
47828 KB |
Output is correct |
18 |
Correct |
246 ms |
49624 KB |
Output is correct |
19 |
Correct |
216 ms |
49740 KB |
Output is correct |
20 |
Correct |
270 ms |
51896 KB |
Output is correct |
21 |
Correct |
157 ms |
47052 KB |
Output is correct |
22 |
Correct |
189 ms |
46944 KB |
Output is correct |
23 |
Correct |
197 ms |
47180 KB |
Output is correct |
24 |
Correct |
193 ms |
49300 KB |
Output is correct |
25 |
Correct |
264 ms |
52300 KB |
Output is correct |
26 |
Correct |
149 ms |
47288 KB |
Output is correct |
27 |
Correct |
170 ms |
46968 KB |
Output is correct |
28 |
Correct |
190 ms |
47340 KB |
Output is correct |
29 |
Correct |
235 ms |
48680 KB |
Output is correct |
30 |
Correct |
250 ms |
50336 KB |
Output is correct |
31 |
Correct |
140 ms |
47256 KB |
Output is correct |
32 |
Correct |
170 ms |
47160 KB |
Output is correct |
33 |
Correct |
185 ms |
47392 KB |
Output is correct |
34 |
Correct |
215 ms |
49248 KB |
Output is correct |
35 |
Correct |
212 ms |
52256 KB |
Output is correct |
36 |
Correct |
216 ms |
49208 KB |
Output is correct |