#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 400
#define mp make_pair
#define mid (l+r)/2
#define Le Node * 2
#define Ri Node * 2 + 1
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
#define all(x) x.begin(), x.end()
#define gc getchar_unlocked
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef pair<double,ll>pdi;
const ll inf=1e18;
const ll Mod=1e9+7;
const ld pai=acos(-1);
ll n , m , q , Root ;
pll E [100009] ;
vpll v [100009] ;
ll Dis [100009] , w [100009] , Dp [100009][20] , Mn [100009][20] , Best [100009] , Yes [100009] ;
void Fill ( ll Node , ll p , ll Sum ) {
Dp [Node][0] = p ;
w [Node] = w [p] + 1 ;
Dis[Node] = Sum ;
Best [Node] = ( Yes [Node] ? Dis [Node] : inf ) ;
for ( auto u : v [Node] ) {
if ( u.fi == p ) C ;
Fill ( u.fi , Node , Sum + u.se ) ;
Best [Node] = min ( Best [Node] , Best [u.fi] ) ;
}
}
ll Check ( ll a , ll b ) {
if ( w [a] < w [b] ) swap ( a , b ) ;
ll l = w [a] - w [b] ;
for ( ll i = 0 ; i < 20 ; i ++ ) {
if ( ( l & ( 1 << i ) ) ) a = Dp [a][i] ;
}
return ( a == b ) ;
}
ll Query ( ll a , ll b ) {
if ( w [a] < w [b] ) swap ( a , b ) ;
ll l = w [a] - w [b] ;
ll ans = Best [a] ;
for ( ll i = 0 ; i < 20 ; i ++ ) {
if ( ( l & ( 1 << i ) ) ) {
ans = min ( ans , Mn [a][i] ) ;
a = Dp [a][i] ;
}
}
return ans ;
}
int main () {
scanf("%lld%lld%lld%lld",&n,&m,&q,&Root) ;
Root -- ;
for ( int i = 0 ; i < n - 1 ; i ++ ) {
ll a , b , c ;
scanf("%lld%lld%lld",&a,&b,&c) ;
a -- , b -- ;
v [a] .pb ( { b , c } ) ;
v [b] .pb ( { a , c } ) ;
E [i] = { a , b } ;
}
for ( ll i = 0 ; i < m ; i ++ ) {
ll x ;
scanf("%lld",&x) , x -- ;
Yes [x] = 1 ;
}
Fill ( Root , Root , 0 ) ;
for ( ll Node = 0 ; Node < n ; Node ++ ) {
Best [Node] += -2 * Dis [Node] ;
}
for ( int Node = 0 ; Node < n ; Node ++ ) {
Mn [Node][0] = min ( Best [Node] , Best [ Dp [Node][0] ] ) ;
}
for ( int j = 1 ; j < 20 ; j ++ ) {
for ( int i = 0 ; i < n ; i ++ ) {
Dp [i][j] = Dp [ Dp [i][j-1] ][j-1] ;
Mn [i][j] = min ( Mn [i][j-1] , Mn [ Dp [i][j-1] ][j-1] ) ;
}
}
for ( int i = 0 ; i < n - 1 ; i ++ ) {
if ( w [ E [i].fi ] > w [ E [i] .se ] ) swap ( E [i].fi , E [i] .se ) ;
}
while ( q -- ) {
int e , b ;
scanf("%d%d",&e,&b) ;
e -- , b -- ;
int a = E [e] .se ;
if ( Check ( a , b ) && w [a] <= w [b] ) {
ll x = min ( Query ( a , b ) , Best [b] ) + Dis [b] ;
if ( x >= 1e17 ) puts("oo");
else printf("%lld\n",x) ;
}
else puts("escaped");
}
}
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld",&n,&m,&q,&Root) ;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:75:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&a,&b,&c) ;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:83:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&x) , x -- ;
~~~~~~~~~~~~~~~~~^~~~~~
valley.cpp:104:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&e,&b) ;
~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
2816 KB |
Output is correct |
2 |
Correct |
9 ms |
2816 KB |
Output is correct |
3 |
Correct |
9 ms |
2944 KB |
Output is correct |
4 |
Correct |
10 ms |
2944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
2816 KB |
Output is correct |
2 |
Correct |
9 ms |
2816 KB |
Output is correct |
3 |
Correct |
9 ms |
2944 KB |
Output is correct |
4 |
Correct |
10 ms |
2944 KB |
Output is correct |
5 |
Correct |
7 ms |
3200 KB |
Output is correct |
6 |
Correct |
7 ms |
3200 KB |
Output is correct |
7 |
Correct |
7 ms |
3200 KB |
Output is correct |
8 |
Correct |
7 ms |
3200 KB |
Output is correct |
9 |
Correct |
9 ms |
3200 KB |
Output is correct |
10 |
Correct |
7 ms |
3200 KB |
Output is correct |
11 |
Correct |
7 ms |
3200 KB |
Output is correct |
12 |
Correct |
8 ms |
3200 KB |
Output is correct |
13 |
Correct |
7 ms |
3200 KB |
Output is correct |
14 |
Correct |
7 ms |
3200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
235 ms |
44668 KB |
Output is correct |
2 |
Correct |
264 ms |
48248 KB |
Output is correct |
3 |
Correct |
307 ms |
48504 KB |
Output is correct |
4 |
Correct |
323 ms |
49956 KB |
Output is correct |
5 |
Correct |
284 ms |
50040 KB |
Output is correct |
6 |
Correct |
309 ms |
51704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
2816 KB |
Output is correct |
2 |
Correct |
9 ms |
2816 KB |
Output is correct |
3 |
Correct |
9 ms |
2944 KB |
Output is correct |
4 |
Correct |
10 ms |
2944 KB |
Output is correct |
5 |
Correct |
7 ms |
3200 KB |
Output is correct |
6 |
Correct |
7 ms |
3200 KB |
Output is correct |
7 |
Correct |
7 ms |
3200 KB |
Output is correct |
8 |
Correct |
7 ms |
3200 KB |
Output is correct |
9 |
Correct |
9 ms |
3200 KB |
Output is correct |
10 |
Correct |
7 ms |
3200 KB |
Output is correct |
11 |
Correct |
7 ms |
3200 KB |
Output is correct |
12 |
Correct |
8 ms |
3200 KB |
Output is correct |
13 |
Correct |
7 ms |
3200 KB |
Output is correct |
14 |
Correct |
7 ms |
3200 KB |
Output is correct |
15 |
Correct |
235 ms |
44668 KB |
Output is correct |
16 |
Correct |
264 ms |
48248 KB |
Output is correct |
17 |
Correct |
307 ms |
48504 KB |
Output is correct |
18 |
Correct |
323 ms |
49956 KB |
Output is correct |
19 |
Correct |
284 ms |
50040 KB |
Output is correct |
20 |
Correct |
309 ms |
51704 KB |
Output is correct |
21 |
Correct |
215 ms |
47224 KB |
Output is correct |
22 |
Correct |
242 ms |
46840 KB |
Output is correct |
23 |
Correct |
250 ms |
47224 KB |
Output is correct |
24 |
Correct |
307 ms |
48888 KB |
Output is correct |
25 |
Correct |
288 ms |
51336 KB |
Output is correct |
26 |
Correct |
200 ms |
47352 KB |
Output is correct |
27 |
Correct |
241 ms |
47228 KB |
Output is correct |
28 |
Correct |
251 ms |
47480 KB |
Output is correct |
29 |
Correct |
296 ms |
48632 KB |
Output is correct |
30 |
Correct |
314 ms |
49916 KB |
Output is correct |
31 |
Correct |
214 ms |
47992 KB |
Output is correct |
32 |
Correct |
254 ms |
47736 KB |
Output is correct |
33 |
Correct |
270 ms |
48072 KB |
Output is correct |
34 |
Correct |
287 ms |
49528 KB |
Output is correct |
35 |
Correct |
279 ms |
51960 KB |
Output is correct |
36 |
Correct |
260 ms |
49528 KB |
Output is correct |