#include <bits/stdc++.h>
using namespace std ;
const long long inf = -1e15 ;
const int MAX = 1e5 + 10 ;
long long tree[4 * MAX] , lazy[4 * MAX] ;
void prop(int node , int l , int r)
{
tree[node] += lazy[node] ;
if(l != r)
{
lazy[node << 1] += lazy[node] ;
lazy[node << 1 | 1] += lazy[node] ;
}
lazy[node] = 0 ;
return ;
}
long long Merge(long long a , long long b)
{
if(a < 0)
return b ;
if(b < 0)
return a ;
return min(a , b) ;
}
void update(int node , int l , int r , int from , int to , long long val)
{
prop(node , l , r) ;
if(from > r || to < l)
return ;
if(l >= from && r <= to)
{
lazy[node] += val ;
prop(node , l , r) ;
return ;
}
int mid = (l + r) >> 1 ;
update(node << 1 , l , mid , from , to , val) ;
update(node << 1 | 1 , mid+1 , r , from , to , val) ;
tree[node] = Merge(tree[node << 1] , tree[node << 1 | 1]) ;
}
long long query(int node , int l , int r , int from , int to)
{
prop(node , l , r) ;
if(from > r || to < l || from > to)
return -1 ;
if(l >= from && r <= to)
return tree[node] ;
int mid = (l + r) >> 1 ;
long long a = query(node << 1 , l , mid , from , to) ;
long long b = query(node << 1 | 1 , mid+1 , r , from , to) ;
return Merge(a , b) ;
}
int u[MAX] , v[MAX] , c[MAX] , mark[MAX] , in[MAX] , out[MAX] ;
int n , s , q , e ;
long long ans[MAX] ;
vector< vector< pair<int , int> > >adj(MAX) , Query(MAX) ;
int tim = 0 ;
void dfs1(int node , int par , long long dist)
{
in[node] = ++tim ;
if(mark[node])
update(1 , 1 , n , in[node] , in[node] , dist) ;
else
update(1 , 1 , n , in[node] , in[node] , inf) ;
for(auto &child : adj[node])
{
if(child.first == par)
continue ;
dfs1(child.first , node , dist+child.second) ;
}
out[node] = tim ;
return ;
}
void dfs2(int node , int par)
{
for(auto &i : Query[node])
{
int x = i.first ;
bool flag1 = (in[node] >= in[v[x]] && in[node] <= out[v[x]]) ;
bool flag2 = (in[e] >= in[v[x]] && in[e] <= out[v[x]]) ;
if(flag1 == flag2)
{
ans[i.second] = -2 ;
continue ;
}
if(flag1)
{
ans[i.second] = query(1 , 1 , n , in[v[x]] , out[v[x]]) ;
if(ans[i.second] < 0)
ans[i.second] = -1 ;
}
else
{
long long a = query(1 , 1 , n , 1 , in[v[x]]-1) ;
long long b = query(1 , 1 , n , out[v[x]]+1 , n) ;
ans[i.second] = Merge(a , b) ;
if(ans[i.second] < 0)
ans[i.second] = -1 ;
}
}
for(auto &child : adj[node])
{
if(child.first == par)
continue ;
update(1 , 1 , n , 1 , n , child.second) ;
update(1 , 1 , n , in[child.first] , out[child.first] , -2ll * child.second) ;
dfs2(child.first , node) ;
update(1 , 1 , n , 1 , n , -1ll * child.second) ;
update(1 , 1 , n , in[child.first] , out[child.first] , 2ll * child.second) ;
}
return ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n>>s>>q>>e ;
for(int i = 1 ; i <= n-1 ; ++i)
{
cin>>u[i]>>v[i]>>c[i] ;
adj[u[i]].emplace_back(v[i] , c[i]) ;
adj[v[i]].emplace_back(u[i] , c[i]) ;
}
for(int i = 0 ; i < s ; ++i)
{
int x ;
cin>>x ;
mark[x] = 1 ;
}
for(int i = 0 ; i < q ; ++i)
{
int x , y ;
cin>>x>>y ;
Query[y].emplace_back(x , i) ;
}
dfs1(1 , -1 , 0) ;
for(int i = 1 ; i <= n-1 ; ++i)
{
if(in[v[i]] < in[u[i]])
swap(u[i] , v[i]) ;
}
dfs2(1 , -1) ;
for(int i = 0 ; i < q ; ++i)
{
if(ans[i] >= 0)
cout<<ans[i]<<"\n" ;
else if(ans[i] == -1)
cout<<"oo\n" ;
else
cout<<"escaped\n" ;
}
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
5504 KB |
Output is correct |
2 |
Correct |
10 ms |
5504 KB |
Output is correct |
3 |
Correct |
11 ms |
5504 KB |
Output is correct |
4 |
Correct |
9 ms |
5376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
5504 KB |
Output is correct |
2 |
Correct |
10 ms |
5504 KB |
Output is correct |
3 |
Correct |
11 ms |
5504 KB |
Output is correct |
4 |
Correct |
9 ms |
5376 KB |
Output is correct |
5 |
Correct |
8 ms |
5248 KB |
Output is correct |
6 |
Correct |
8 ms |
5248 KB |
Output is correct |
7 |
Correct |
9 ms |
5248 KB |
Output is correct |
8 |
Correct |
9 ms |
5248 KB |
Output is correct |
9 |
Correct |
10 ms |
5376 KB |
Output is correct |
10 |
Correct |
9 ms |
5248 KB |
Output is correct |
11 |
Correct |
9 ms |
5248 KB |
Output is correct |
12 |
Correct |
9 ms |
5248 KB |
Output is correct |
13 |
Correct |
8 ms |
5248 KB |
Output is correct |
14 |
Correct |
9 ms |
5248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
282 ms |
23032 KB |
Output is correct |
2 |
Correct |
284 ms |
22496 KB |
Output is correct |
3 |
Correct |
274 ms |
22396 KB |
Output is correct |
4 |
Correct |
308 ms |
24184 KB |
Output is correct |
5 |
Correct |
250 ms |
23288 KB |
Output is correct |
6 |
Correct |
309 ms |
27388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
5504 KB |
Output is correct |
2 |
Correct |
10 ms |
5504 KB |
Output is correct |
3 |
Correct |
11 ms |
5504 KB |
Output is correct |
4 |
Correct |
9 ms |
5376 KB |
Output is correct |
5 |
Correct |
8 ms |
5248 KB |
Output is correct |
6 |
Correct |
8 ms |
5248 KB |
Output is correct |
7 |
Correct |
9 ms |
5248 KB |
Output is correct |
8 |
Correct |
9 ms |
5248 KB |
Output is correct |
9 |
Correct |
10 ms |
5376 KB |
Output is correct |
10 |
Correct |
9 ms |
5248 KB |
Output is correct |
11 |
Correct |
9 ms |
5248 KB |
Output is correct |
12 |
Correct |
9 ms |
5248 KB |
Output is correct |
13 |
Correct |
8 ms |
5248 KB |
Output is correct |
14 |
Correct |
9 ms |
5248 KB |
Output is correct |
15 |
Correct |
282 ms |
23032 KB |
Output is correct |
16 |
Correct |
284 ms |
22496 KB |
Output is correct |
17 |
Correct |
274 ms |
22396 KB |
Output is correct |
18 |
Correct |
308 ms |
24184 KB |
Output is correct |
19 |
Correct |
250 ms |
23288 KB |
Output is correct |
20 |
Correct |
309 ms |
27388 KB |
Output is correct |
21 |
Correct |
246 ms |
21884 KB |
Output is correct |
22 |
Correct |
264 ms |
21624 KB |
Output is correct |
23 |
Correct |
263 ms |
21496 KB |
Output is correct |
24 |
Correct |
291 ms |
22904 KB |
Output is correct |
25 |
Correct |
291 ms |
25720 KB |
Output is correct |
26 |
Correct |
250 ms |
22136 KB |
Output is correct |
27 |
Correct |
282 ms |
21752 KB |
Output is correct |
28 |
Correct |
266 ms |
21752 KB |
Output is correct |
29 |
Correct |
281 ms |
23544 KB |
Output is correct |
30 |
Correct |
293 ms |
24884 KB |
Output is correct |
31 |
Correct |
252 ms |
22392 KB |
Output is correct |
32 |
Correct |
275 ms |
22040 KB |
Output is correct |
33 |
Correct |
269 ms |
22008 KB |
Output is correct |
34 |
Correct |
299 ms |
23288 KB |
Output is correct |
35 |
Correct |
287 ms |
25336 KB |
Output is correct |
36 |
Correct |
278 ms |
23544 KB |
Output is correct |