#include <bits/stdc++.h>
using namespace std;
struct edge {
int u, v, w;
int other( int x ) {
return u ^ v ^ x;
}
};
struct query {
int v, e;
};
struct SegTree {
int l, r;
long long zero;
vector<long long> aint;
void init( int _l, int _r, long long _zero ) {
l = _l;
r = _r;
zero = _zero;
aint.resize( 4 * (r - l + 1) );
for ( int v = 0; v < aint.size(); v++ )
aint[v] = zero;
}
void update( int v, int l, int r, int p, long long x ) {
if ( l > p || r < p )
return;
if ( l == r ) {
aint[v] = x;
return;
}
int mid = (l + r) / 2;
update( v * 2 + 1, l, mid, p, x );
update( v * 2 + 2, mid + 1, r, p, x );
aint[v] = min( aint[v * 2 + 1], aint[v * 2 + 2] );
}
void update( int p, long long x ) {
update( 0, l, r, p, x );
}
long long query( int v, int l, int r, int lq, int rq ) {
if ( l > rq || r < lq )
return zero;
if ( lq <= l && r <= rq )
return aint[v];
int mid = (l + r) / 2;
return min( query( v * 2 + 1, l, mid, lq, rq ), query( v * 2 + 2, mid + 1, r, lq, rq ) );
}
long long query( int lq, int rq ) {
return query( 0, l, r, lq, rq );
}
};
const int MAX_N = 1e5;
const int MAX_Q = 1e5;
const long long INF = 1e15;
bool isShop[MAX_N + 1];
int pos[MAX_N + 1];
long long depth[MAX_N + 1], distShop[MAX_N + 1], ans[MAX_Q + 1];
edge edges[MAX_N];
query queries[MAX_Q];
vector<int> adj[MAX_N + 1], queriesByVert[MAX_N + 1];
SegTree minDist;
void calc( int u, int p ) {
distShop[u] = (isShop[u] ? 0 : INF);
for ( int e: adj[u] ) {
int v = edges[e].other( u ), w = edges[e].w;
if ( v == p )
continue;
depth[v] = depth[u] + w;
calc( v, u );
distShop[u] = min( distShop[u], distShop[v] + w );
}
}
void solve( int u, int p, int d ) {
minDist.update( d, distShop[u] - depth[u] );
pos[u] = d;
for ( int e: adj[u] ) {
int v = edges[e].other( u );
if ( v == p )
continue;
solve( v, u, d + 1 );
}
for ( int q: queriesByVert[u] ) {
int v = (depth[edges[queries[q].e].u] < depth[edges[queries[q].e].v] ? edges[queries[q].e].v : edges[queries[q].e].u);
if ( pos[v] == 0 )
ans[q] = -1;
else
ans[q] = minDist.query( pos[v], pos[u] ) + depth[u];
}
minDist.update( d, INF );
pos[u] = 0;
}
int main() {
int n, s, q, e;
cin >> n >> s >> q >> e;
for ( int i = 1; i <= n - 1; i++ ) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
adj[edges[i].u].push_back( i );
adj[edges[i].v].push_back( i );
}
for ( int i = 0; i < s; i++ ) {
int v;
cin >> v;
isShop[v] = true;
}
for ( int i = 0; i < q; i++ ) {
cin >> queries[i].e >> queries[i].v;
queriesByVert[queries[i].v].push_back( i );
}
minDist.init( 1, n, INF );
calc( e, 0 );
solve( e, 0, 1 );
for ( int i = 0; i < q; i++ ) {
if ( ans[i] == -1 )
cout << "escaped\n";
else if ( ans[i] == INF )
cout << "oo\n";
else
cout << ans[i] << "\n";
}
return 0;
}
Compilation message
valley.cpp: In member function 'void SegTree::init(int, int, long long int)':
valley.cpp:27:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for ( int v = 0; v < aint.size(); v++ )
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8796 KB |
Output is correct |
2 |
Correct |
5 ms |
9052 KB |
Output is correct |
3 |
Correct |
5 ms |
8796 KB |
Output is correct |
4 |
Correct |
6 ms |
8792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8796 KB |
Output is correct |
2 |
Correct |
5 ms |
9052 KB |
Output is correct |
3 |
Correct |
5 ms |
8796 KB |
Output is correct |
4 |
Correct |
6 ms |
8792 KB |
Output is correct |
5 |
Correct |
4 ms |
8796 KB |
Output is correct |
6 |
Correct |
4 ms |
8796 KB |
Output is correct |
7 |
Correct |
3 ms |
8796 KB |
Output is correct |
8 |
Correct |
3 ms |
8796 KB |
Output is correct |
9 |
Correct |
4 ms |
8828 KB |
Output is correct |
10 |
Correct |
3 ms |
8796 KB |
Output is correct |
11 |
Correct |
3 ms |
9048 KB |
Output is correct |
12 |
Correct |
3 ms |
8888 KB |
Output is correct |
13 |
Correct |
3 ms |
8796 KB |
Output is correct |
14 |
Correct |
3 ms |
8796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
232 ms |
22872 KB |
Output is correct |
2 |
Correct |
211 ms |
22444 KB |
Output is correct |
3 |
Correct |
223 ms |
22556 KB |
Output is correct |
4 |
Correct |
245 ms |
27104 KB |
Output is correct |
5 |
Correct |
218 ms |
25428 KB |
Output is correct |
6 |
Correct |
245 ms |
30904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8796 KB |
Output is correct |
2 |
Correct |
5 ms |
9052 KB |
Output is correct |
3 |
Correct |
5 ms |
8796 KB |
Output is correct |
4 |
Correct |
6 ms |
8792 KB |
Output is correct |
5 |
Correct |
4 ms |
8796 KB |
Output is correct |
6 |
Correct |
4 ms |
8796 KB |
Output is correct |
7 |
Correct |
3 ms |
8796 KB |
Output is correct |
8 |
Correct |
3 ms |
8796 KB |
Output is correct |
9 |
Correct |
4 ms |
8828 KB |
Output is correct |
10 |
Correct |
3 ms |
8796 KB |
Output is correct |
11 |
Correct |
3 ms |
9048 KB |
Output is correct |
12 |
Correct |
3 ms |
8888 KB |
Output is correct |
13 |
Correct |
3 ms |
8796 KB |
Output is correct |
14 |
Correct |
3 ms |
8796 KB |
Output is correct |
15 |
Correct |
232 ms |
22872 KB |
Output is correct |
16 |
Correct |
211 ms |
22444 KB |
Output is correct |
17 |
Correct |
223 ms |
22556 KB |
Output is correct |
18 |
Correct |
245 ms |
27104 KB |
Output is correct |
19 |
Correct |
218 ms |
25428 KB |
Output is correct |
20 |
Correct |
245 ms |
30904 KB |
Output is correct |
21 |
Correct |
186 ms |
22096 KB |
Output is correct |
22 |
Correct |
221 ms |
21904 KB |
Output is correct |
23 |
Correct |
207 ms |
21736 KB |
Output is correct |
24 |
Correct |
212 ms |
26660 KB |
Output is correct |
25 |
Correct |
218 ms |
32112 KB |
Output is correct |
26 |
Correct |
190 ms |
22096 KB |
Output is correct |
27 |
Correct |
204 ms |
21844 KB |
Output is correct |
28 |
Correct |
226 ms |
21984 KB |
Output is correct |
29 |
Correct |
209 ms |
25168 KB |
Output is correct |
30 |
Correct |
210 ms |
27444 KB |
Output is correct |
31 |
Correct |
224 ms |
22352 KB |
Output is correct |
32 |
Correct |
207 ms |
22100 KB |
Output is correct |
33 |
Correct |
220 ms |
22204 KB |
Output is correct |
34 |
Correct |
271 ms |
26292 KB |
Output is correct |
35 |
Correct |
203 ms |
32032 KB |
Output is correct |
36 |
Correct |
189 ms |
25940 KB |
Output is correct |