#include <bits/stdc++.h>
using namespace std;
const long long MX=2e5+10;
const long long INF=1e18;
const long long lg=20;
vector < pair < long long , long long > > mas[MX];
long long a[MX],b[MX],god[MX];
long long h[MX],d[MX];
long long tin[MX],tou[MX],timer=0;
long long mans[lg][MX],lca[lg][MX];
void DFS(int zar)
{
timer++;
tin[zar]=timer;
for(int i=1;i<lg;i++)
{
lca[i][zar]=lca[i-1][lca[i-1][zar]];
}
d[zar]=(!god[zar])*INF;
for(auto [u,w]:mas[zar])
{
if(u!=lca[0][zar])
{
h[u]=h[zar]+w;
lca[0][u]=zar;
DFS(u);
d[zar]=min(d[zar],d[u]+w);
}
}
mans[0][zar]=d[zar]-h[zar];
timer++;
tou[zar]=timer;
}
bool prd(long long pr,long long s)
{
return (tin[pr]<=tin[s] && tou[s]<=tou[pr]);
}
void fun(long long in,long long zn)
{
if(!prd(b[in],zn))
{
cout<<"escaped\n";
return;
}
if(d[b[in]]==INF)
{
cout<<"oo\n";
return;
}
long long ans=mans[0][b[in]],zar=zn;
for(int i=lg-1;i>=0;i--)
{
if(prd(b[in],lca[i][zar]))
{
ans=min(ans,mans[i][zar]);
zar=lca[i][zar];
}
}
cout<<ans+h[zn]<<"\n";
}
int main()
{
cin.tie(0);
ios_base::sync_with_stdio(0);
long long n,s,q,e;
cin>>n>>s>>q>>e;
for(long long i=1;i<n;i++)
{
long long w;
cin>>a[i]>>b[i]>>w;
mas[a[i]].push_back({b[i],w});
mas[b[i]].push_back({a[i],w});
}
for(long long i=1;i<=s;i++)
{
long long o;
cin>>o;
god[o]=1;
}
lca[0][e]=e;
DFS(e);
for(long long i=1;i<n;i++)
{
if(tin[a[i]]>tin[b[i]])
{
swap(a[i],b[i]);
}
}
for(long long j=1;j<lg;j++)
{
for(long long i=1;i<=n;i++)
{
mans[j][i]=min(mans[j-1][i],mans[j-1][lca[j-1][i]]);
}
}
while(q--)
{
long long id,zn;
cin>>id>>zn;
fun(id,zn);
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
74520 KB |
Output is correct |
2 |
Correct |
10 ms |
74588 KB |
Output is correct |
3 |
Correct |
11 ms |
74588 KB |
Output is correct |
4 |
Correct |
10 ms |
74584 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
74520 KB |
Output is correct |
2 |
Correct |
10 ms |
74588 KB |
Output is correct |
3 |
Correct |
11 ms |
74588 KB |
Output is correct |
4 |
Correct |
10 ms |
74584 KB |
Output is correct |
5 |
Correct |
10 ms |
74464 KB |
Output is correct |
6 |
Correct |
9 ms |
74584 KB |
Output is correct |
7 |
Correct |
9 ms |
74588 KB |
Output is correct |
8 |
Correct |
10 ms |
74588 KB |
Output is correct |
9 |
Correct |
9 ms |
74584 KB |
Output is correct |
10 |
Correct |
10 ms |
74456 KB |
Output is correct |
11 |
Correct |
9 ms |
74588 KB |
Output is correct |
12 |
Correct |
9 ms |
74588 KB |
Output is correct |
13 |
Correct |
10 ms |
74588 KB |
Output is correct |
14 |
Correct |
10 ms |
74564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
124 ms |
83264 KB |
Output is correct |
2 |
Correct |
128 ms |
86884 KB |
Output is correct |
3 |
Correct |
137 ms |
86456 KB |
Output is correct |
4 |
Correct |
134 ms |
88916 KB |
Output is correct |
5 |
Correct |
116 ms |
89008 KB |
Output is correct |
6 |
Correct |
151 ms |
91220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
74520 KB |
Output is correct |
2 |
Correct |
10 ms |
74588 KB |
Output is correct |
3 |
Correct |
11 ms |
74588 KB |
Output is correct |
4 |
Correct |
10 ms |
74584 KB |
Output is correct |
5 |
Correct |
10 ms |
74464 KB |
Output is correct |
6 |
Correct |
9 ms |
74584 KB |
Output is correct |
7 |
Correct |
9 ms |
74588 KB |
Output is correct |
8 |
Correct |
10 ms |
74588 KB |
Output is correct |
9 |
Correct |
9 ms |
74584 KB |
Output is correct |
10 |
Correct |
10 ms |
74456 KB |
Output is correct |
11 |
Correct |
9 ms |
74588 KB |
Output is correct |
12 |
Correct |
9 ms |
74588 KB |
Output is correct |
13 |
Correct |
10 ms |
74588 KB |
Output is correct |
14 |
Correct |
10 ms |
74564 KB |
Output is correct |
15 |
Correct |
124 ms |
83264 KB |
Output is correct |
16 |
Correct |
128 ms |
86884 KB |
Output is correct |
17 |
Correct |
137 ms |
86456 KB |
Output is correct |
18 |
Correct |
134 ms |
88916 KB |
Output is correct |
19 |
Correct |
116 ms |
89008 KB |
Output is correct |
20 |
Correct |
151 ms |
91220 KB |
Output is correct |
21 |
Correct |
90 ms |
86612 KB |
Output is correct |
22 |
Correct |
100 ms |
86608 KB |
Output is correct |
23 |
Correct |
109 ms |
86632 KB |
Output is correct |
24 |
Correct |
112 ms |
88828 KB |
Output is correct |
25 |
Correct |
147 ms |
91728 KB |
Output is correct |
26 |
Correct |
87 ms |
86540 KB |
Output is correct |
27 |
Correct |
107 ms |
86392 KB |
Output is correct |
28 |
Correct |
114 ms |
86608 KB |
Output is correct |
29 |
Correct |
127 ms |
88308 KB |
Output is correct |
30 |
Correct |
143 ms |
89824 KB |
Output is correct |
31 |
Correct |
101 ms |
86736 KB |
Output is correct |
32 |
Correct |
104 ms |
86608 KB |
Output is correct |
33 |
Correct |
105 ms |
86684 KB |
Output is correct |
34 |
Correct |
172 ms |
88692 KB |
Output is correct |
35 |
Correct |
145 ms |
90900 KB |
Output is correct |
36 |
Correct |
128 ms |
88816 KB |
Output is correct |