#include <bits/stdc++.h>
#define pii pair<long long, long long>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 10;
int n, S, q, E, in[N], out[N], pos[N], dep[N], par[N][20], s[N], e[N], shop[N];
long long d[N], dp[N], ans[N][20];
vector<pii> g[N];
void dfs( int u, int p ) {
static int idx = 0;
in[u] = ++idx, pos[idx] = u;
dep[u] = dep[p] + 1, par[u][0] = p;
if( shop[u] ) dp[u] = d[u];
for( pii v : g[u] ) if( v.x != p ) {
d[v.x] = d[u] + v.y;
dfs( v.x, u );
dp[u] = min( dp[u], dp[v.x] );
}
out[u] = idx;
}
int main()
{
fill_n( dp, N, 1e18 ), fill_n( ans[0], N * 20, 1e18 );
scanf("%d %d %d %d",&n,&S,&q,&E);
for( int i = 1 ; i < n ; i++ ) {
long long dd;
scanf("%d %d %lld",&s[i],&e[i],&dd);
g[s[i]].emplace_back( pii( e[i], dd ) ), g[e[i]].emplace_back( pii( s[i], dd ) );
}
for( int i = 1, ss ; i <= S ; i++ ) {
scanf("%d",&ss);
shop[ss] = 1;
}
dfs( E, 0 );
for( int i = 1 ; i <= n ; i++ ) if( dp[i] != 1e18 ) ans[i][0] = dp[i] - 2*d[i];
for( int i = 1 ; i <= 17 ; i++ ) {
for( int j = 1 ; j <= n ; j++ ) {
par[j][i] = par[par[j][i-1]][i-1];
ans[j][i] = min( ans[j][i-1], ans[par[j][i-1]][i-1] );
}
}
for( int i = 1, a, b ; i <= q ; i++ ) {
scanf("%d %d",&a,&b);
int now = dep[s[a]] > dep[e[a]] ? s[a] : e[a];
if( in[now] > in[b] || out[b] > out[now] ) {
printf("escaped\n");
continue;
}
int dist = dep[b] - dep[now], u = b;
long long an = 1e18;
for( int i = 17 ; i >= 0 ; i-- ) if( dist >> i & 1 ) {
an = min( an, ans[u][i] );
u = par[u][i];
}
an = min( an, ans[u][0] );
if( an >= 1e18 ) printf("oo\n");
else printf("%lld\n", an + d[b]);
}
return 0;
}
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&n,&S,&q,&E);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld",&s[i],&e[i],&dd);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&ss);
~~~~~^~~~~~~~~~
valley.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a,&b);
~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
19328 KB |
Output is correct |
2 |
Correct |
17 ms |
19328 KB |
Output is correct |
3 |
Correct |
17 ms |
19328 KB |
Output is correct |
4 |
Correct |
17 ms |
19328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
19328 KB |
Output is correct |
2 |
Correct |
17 ms |
19328 KB |
Output is correct |
3 |
Correct |
17 ms |
19328 KB |
Output is correct |
4 |
Correct |
17 ms |
19328 KB |
Output is correct |
5 |
Correct |
14 ms |
19328 KB |
Output is correct |
6 |
Correct |
14 ms |
19328 KB |
Output is correct |
7 |
Correct |
15 ms |
19328 KB |
Output is correct |
8 |
Correct |
14 ms |
19328 KB |
Output is correct |
9 |
Correct |
14 ms |
19328 KB |
Output is correct |
10 |
Correct |
14 ms |
19328 KB |
Output is correct |
11 |
Correct |
14 ms |
19328 KB |
Output is correct |
12 |
Correct |
14 ms |
19456 KB |
Output is correct |
13 |
Correct |
15 ms |
19456 KB |
Output is correct |
14 |
Correct |
14 ms |
19328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
205 ms |
40200 KB |
Output is correct |
2 |
Correct |
207 ms |
39928 KB |
Output is correct |
3 |
Correct |
219 ms |
40184 KB |
Output is correct |
4 |
Correct |
243 ms |
41592 KB |
Output is correct |
5 |
Correct |
217 ms |
41976 KB |
Output is correct |
6 |
Correct |
248 ms |
43384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
19328 KB |
Output is correct |
2 |
Correct |
17 ms |
19328 KB |
Output is correct |
3 |
Correct |
17 ms |
19328 KB |
Output is correct |
4 |
Correct |
17 ms |
19328 KB |
Output is correct |
5 |
Correct |
14 ms |
19328 KB |
Output is correct |
6 |
Correct |
14 ms |
19328 KB |
Output is correct |
7 |
Correct |
15 ms |
19328 KB |
Output is correct |
8 |
Correct |
14 ms |
19328 KB |
Output is correct |
9 |
Correct |
14 ms |
19328 KB |
Output is correct |
10 |
Correct |
14 ms |
19328 KB |
Output is correct |
11 |
Correct |
14 ms |
19328 KB |
Output is correct |
12 |
Correct |
14 ms |
19456 KB |
Output is correct |
13 |
Correct |
15 ms |
19456 KB |
Output is correct |
14 |
Correct |
14 ms |
19328 KB |
Output is correct |
15 |
Correct |
205 ms |
40200 KB |
Output is correct |
16 |
Correct |
207 ms |
39928 KB |
Output is correct |
17 |
Correct |
219 ms |
40184 KB |
Output is correct |
18 |
Correct |
243 ms |
41592 KB |
Output is correct |
19 |
Correct |
217 ms |
41976 KB |
Output is correct |
20 |
Correct |
248 ms |
43384 KB |
Output is correct |
21 |
Correct |
173 ms |
39264 KB |
Output is correct |
22 |
Correct |
185 ms |
39032 KB |
Output is correct |
23 |
Correct |
196 ms |
39164 KB |
Output is correct |
24 |
Correct |
209 ms |
40952 KB |
Output is correct |
25 |
Correct |
211 ms |
43384 KB |
Output is correct |
26 |
Correct |
174 ms |
39544 KB |
Output is correct |
27 |
Correct |
183 ms |
39288 KB |
Output is correct |
28 |
Correct |
193 ms |
39544 KB |
Output is correct |
29 |
Correct |
211 ms |
40696 KB |
Output is correct |
30 |
Correct |
231 ms |
42104 KB |
Output is correct |
31 |
Correct |
183 ms |
39800 KB |
Output is correct |
32 |
Correct |
190 ms |
39544 KB |
Output is correct |
33 |
Correct |
199 ms |
39900 KB |
Output is correct |
34 |
Correct |
225 ms |
41464 KB |
Output is correct |
35 |
Correct |
220 ms |
43640 KB |
Output is correct |
36 |
Correct |
197 ms |
41336 KB |
Output is correct |