#include<bits/stdc++.h>
using namespace std;
long long n , s , q , e , dp [100005] , pr [100005] , st [100005][23] , sum [100005] , stt [100005][23];
vector < pair < int , int > > gr [100005] , edg;
void go ( int x , int p )
{
dp [x] = dp [p] + 1;
st [x][0] = p;
for ( auto xx : gr [x] )
{
int u = xx . first;
if ( u == p ) continue;
sum [u] = sum [x] + xx . second;
go ( u , x );
stt [x][0] = min ( stt [x][0] , stt [u][0] + xx . second );
}
}
int lca ( int x , int y )
{
if ( dp [x] > dp [y] ) swap ( x , y );
int dif = dp [y] - dp [x];
for ( int i = 0 ; i < 21 ; i ++ )
{
if ( ( dif & ( 1 << i ) ) ) y = st [y][i];
}
if ( x == y ) return x;
for ( int i = 21 ; i >= 0 ; i -- )
{
if ( st [x][i] != st [y][i] )
{
x = st [x][i];
y = st [y][i];
}
}
return st [x][0];
}
int main()
{
cin >> n >> s >> q >> e;
for ( int i = 0 ; i < n - 1 ; i ++ )
{
int x , y , z;
cin >> x >> y >> z;
edg . push_back ( { x , y } );
gr [x] . push_back ( { y , z } );
gr [y] . push_back ( { x , z } );
}
for ( int i = 1 ; i <= n ; i ++ ) stt [i][0] = 1e16;
for ( int i = 0 ; i < s ; i ++ )
{
int x;
cin >> x;
stt [x][0] = 0;
}
go ( e , 0 );
for ( int i = 1 ; i <= 21 ; i ++ )
{
for ( int j = 1 ; j <= n ; j ++ )
{
long long nxt = st [j][ i - 1 ] , dis = sum [j] - sum [nxt];
st [j][i] = st [nxt][ i - 1 ];
stt [j][i] = min ( stt [j][ i - 1 ] , stt [nxt][ i - 1 ] + dis );
}
}
while ( q -- )
{
int x , y;
cin >> x >> y;
int a = edg [ x - 1 ] . first , b = edg [ x - 1 ] . second;
if ( dp [a] < dp [b] ) a = b;
if ( lca ( y , a ) != a )
{
cout << "escaped" << endl;
continue;
}
long long dif = dp [y] - dp [a] + 1 , ans = 1e17 , oy = y;
for ( int i = 0 ; i <= 21 ; i ++ )
{
if ( ( dif & ( 1 << i ) ) )
{
long long ad = sum [oy] - sum [y];
ans = min ( ans , ad + stt [y][i] );
y = st [y][i];
}
}
if ( ans >= 1e16 ) cout << "oo" << endl;
else cout << ans << endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
2824 KB |
Output is correct |
2 |
Correct |
18 ms |
2844 KB |
Output is correct |
3 |
Correct |
19 ms |
2836 KB |
Output is correct |
4 |
Correct |
18 ms |
2804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
2824 KB |
Output is correct |
2 |
Correct |
18 ms |
2844 KB |
Output is correct |
3 |
Correct |
19 ms |
2836 KB |
Output is correct |
4 |
Correct |
18 ms |
2804 KB |
Output is correct |
5 |
Correct |
5 ms |
3056 KB |
Output is correct |
6 |
Correct |
5 ms |
3048 KB |
Output is correct |
7 |
Correct |
5 ms |
3156 KB |
Output is correct |
8 |
Correct |
4 ms |
3028 KB |
Output is correct |
9 |
Correct |
4 ms |
3028 KB |
Output is correct |
10 |
Correct |
5 ms |
3028 KB |
Output is correct |
11 |
Correct |
6 ms |
3156 KB |
Output is correct |
12 |
Correct |
4 ms |
3028 KB |
Output is correct |
13 |
Correct |
5 ms |
3156 KB |
Output is correct |
14 |
Correct |
6 ms |
3156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
415 ms |
49436 KB |
Output is correct |
2 |
Correct |
424 ms |
49004 KB |
Output is correct |
3 |
Correct |
430 ms |
48960 KB |
Output is correct |
4 |
Correct |
470 ms |
51096 KB |
Output is correct |
5 |
Correct |
437 ms |
51272 KB |
Output is correct |
6 |
Correct |
474 ms |
53648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
2824 KB |
Output is correct |
2 |
Correct |
18 ms |
2844 KB |
Output is correct |
3 |
Correct |
19 ms |
2836 KB |
Output is correct |
4 |
Correct |
18 ms |
2804 KB |
Output is correct |
5 |
Correct |
5 ms |
3056 KB |
Output is correct |
6 |
Correct |
5 ms |
3048 KB |
Output is correct |
7 |
Correct |
5 ms |
3156 KB |
Output is correct |
8 |
Correct |
4 ms |
3028 KB |
Output is correct |
9 |
Correct |
4 ms |
3028 KB |
Output is correct |
10 |
Correct |
5 ms |
3028 KB |
Output is correct |
11 |
Correct |
6 ms |
3156 KB |
Output is correct |
12 |
Correct |
4 ms |
3028 KB |
Output is correct |
13 |
Correct |
5 ms |
3156 KB |
Output is correct |
14 |
Correct |
6 ms |
3156 KB |
Output is correct |
15 |
Correct |
415 ms |
49436 KB |
Output is correct |
16 |
Correct |
424 ms |
49004 KB |
Output is correct |
17 |
Correct |
430 ms |
48960 KB |
Output is correct |
18 |
Correct |
470 ms |
51096 KB |
Output is correct |
19 |
Correct |
437 ms |
51272 KB |
Output is correct |
20 |
Correct |
474 ms |
53648 KB |
Output is correct |
21 |
Correct |
398 ms |
48908 KB |
Output is correct |
22 |
Correct |
377 ms |
48492 KB |
Output is correct |
23 |
Correct |
399 ms |
48496 KB |
Output is correct |
24 |
Correct |
423 ms |
50876 KB |
Output is correct |
25 |
Correct |
454 ms |
54332 KB |
Output is correct |
26 |
Correct |
372 ms |
48876 KB |
Output is correct |
27 |
Correct |
399 ms |
48488 KB |
Output is correct |
28 |
Correct |
404 ms |
48572 KB |
Output is correct |
29 |
Correct |
429 ms |
50108 KB |
Output is correct |
30 |
Correct |
456 ms |
51852 KB |
Output is correct |
31 |
Correct |
379 ms |
48960 KB |
Output is correct |
32 |
Correct |
389 ms |
48612 KB |
Output is correct |
33 |
Correct |
415 ms |
48728 KB |
Output is correct |
34 |
Correct |
438 ms |
50852 KB |
Output is correct |
35 |
Correct |
461 ms |
54064 KB |
Output is correct |
36 |
Correct |
399 ms |
51008 KB |
Output is correct |