/* Murad Eynizade */
#include <bits/stdc++.h>
#define intt long long
#define fyck ios_base::sync_with_stdio(0);cin.tie(0);
#define F first
#define S second
//#define endl '\n'
using namespace std;
const int maxx = 100001 , lg = 17;
int n , m , q , ex , nxt;
int lvl[maxx] , in[maxx] , dp[maxx] , shop[maxx] , cnt[maxx];
intt dist[maxx] , table[maxx][lg] , close[maxx] , par[maxx][lg];
vector< pair<int,intt> >v[maxx] , arr;
void dfs(int s,int p) {
dp[s] = 1;
cnt[s] = shop[s];
par[s][0] = p;
in[s] = ++nxt;
lvl[s] = lvl[p] + 1;
for (auto to : v[s])
if (to.F != p) dist[to.F] = dist[s] + to.S , dfs(to.F , s) , dp[s] += dp[to.F] , cnt[s] += cnt[to.F];
}
void build(int s,int p) {
if (shop[s])close[s] = dist[s];
else close[s] = 1000000000000000LL;
for (auto to : v[s]) {
if (to.F == p)continue;
build(to.F , s);
close[s] = min(close[s] , close[to.F]);
}
}
int x , y , w;
int main() {
fyck
cin>>n>>m>>q>>ex;
for (int i = 1;i<n;i++) {
cin>>x>>y>>w;
v[x].push_back({y , w});
v[y].push_back({x , w});
arr.push_back({x , y});
}
for (int i = 1;i<=m;i++)cin>>x , shop[x] = 1;
dfs(ex , 0);
build(ex , 0);
for (int i = 1;i<=n;i++)close[i] -= 2 * dist[i] , table[i][0] = close[i];
for (int j = 1;j<lg;j++)
for (int i = 1;i<=n;i++)
par[i][j] = par[par[i][j - 1]][j - 1];
for (int j = 1;j<lg;j++)
for (int i = 1;i<=n;i++)
table[i][j] = min(table[i][j - 1],table[par[i][j - 1]][j - 1]);
int i , r;
while (q--) {
cin>>i>>r;
i--;
x = arr[i].F; y = arr[i].S;
if (lvl[x] < lvl[y])swap(x , y);
intt res = (in[r] >= in[x] && in[r] <= in[x] + dp[x] - 1);
if (!res)cout<<"escaped"<<endl;
else if (cnt[x] == 0)cout<<"oo"<<endl;
else {
intt res = 1000000000000000LL , re = dist[r];
int diff = lvl[r] - lvl[x];
for (int i = 0;i<lg;i++) {
if ((1 << i) & diff) {
res = min(res , table[r][i]);
r = par[r][i];
}
}
res = min(res , table[r][0]);
cout<<res + re<<endl;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
2940 KB |
Output is correct |
2 |
Correct |
32 ms |
2960 KB |
Output is correct |
3 |
Correct |
32 ms |
2868 KB |
Output is correct |
4 |
Correct |
34 ms |
2936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
2940 KB |
Output is correct |
2 |
Correct |
32 ms |
2960 KB |
Output is correct |
3 |
Correct |
32 ms |
2868 KB |
Output is correct |
4 |
Correct |
34 ms |
2936 KB |
Output is correct |
5 |
Correct |
8 ms |
3192 KB |
Output is correct |
6 |
Correct |
8 ms |
3192 KB |
Output is correct |
7 |
Correct |
8 ms |
3192 KB |
Output is correct |
8 |
Correct |
8 ms |
3064 KB |
Output is correct |
9 |
Correct |
8 ms |
3192 KB |
Output is correct |
10 |
Correct |
8 ms |
3192 KB |
Output is correct |
11 |
Correct |
8 ms |
3064 KB |
Output is correct |
12 |
Correct |
8 ms |
3124 KB |
Output is correct |
13 |
Correct |
8 ms |
3192 KB |
Output is correct |
14 |
Correct |
8 ms |
3192 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
528 ms |
43848 KB |
Output is correct |
2 |
Correct |
498 ms |
43656 KB |
Output is correct |
3 |
Correct |
517 ms |
43776 KB |
Output is correct |
4 |
Correct |
548 ms |
45272 KB |
Output is correct |
5 |
Correct |
527 ms |
45520 KB |
Output is correct |
6 |
Correct |
571 ms |
47288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
2940 KB |
Output is correct |
2 |
Correct |
32 ms |
2960 KB |
Output is correct |
3 |
Correct |
32 ms |
2868 KB |
Output is correct |
4 |
Correct |
34 ms |
2936 KB |
Output is correct |
5 |
Correct |
8 ms |
3192 KB |
Output is correct |
6 |
Correct |
8 ms |
3192 KB |
Output is correct |
7 |
Correct |
8 ms |
3192 KB |
Output is correct |
8 |
Correct |
8 ms |
3064 KB |
Output is correct |
9 |
Correct |
8 ms |
3192 KB |
Output is correct |
10 |
Correct |
8 ms |
3192 KB |
Output is correct |
11 |
Correct |
8 ms |
3064 KB |
Output is correct |
12 |
Correct |
8 ms |
3124 KB |
Output is correct |
13 |
Correct |
8 ms |
3192 KB |
Output is correct |
14 |
Correct |
8 ms |
3192 KB |
Output is correct |
15 |
Correct |
528 ms |
43848 KB |
Output is correct |
16 |
Correct |
498 ms |
43656 KB |
Output is correct |
17 |
Correct |
517 ms |
43776 KB |
Output is correct |
18 |
Correct |
548 ms |
45272 KB |
Output is correct |
19 |
Correct |
527 ms |
45520 KB |
Output is correct |
20 |
Correct |
571 ms |
47288 KB |
Output is correct |
21 |
Correct |
468 ms |
43172 KB |
Output is correct |
22 |
Correct |
491 ms |
42956 KB |
Output is correct |
23 |
Correct |
521 ms |
43272 KB |
Output is correct |
24 |
Correct |
518 ms |
44928 KB |
Output is correct |
25 |
Correct |
544 ms |
47384 KB |
Output is correct |
26 |
Correct |
486 ms |
43576 KB |
Output is correct |
27 |
Correct |
480 ms |
43192 KB |
Output is correct |
28 |
Correct |
504 ms |
43440 KB |
Output is correct |
29 |
Correct |
506 ms |
44640 KB |
Output is correct |
30 |
Correct |
546 ms |
46092 KB |
Output is correct |
31 |
Correct |
460 ms |
42340 KB |
Output is correct |
32 |
Correct |
494 ms |
40324 KB |
Output is correct |
33 |
Correct |
488 ms |
40476 KB |
Output is correct |
34 |
Correct |
540 ms |
42472 KB |
Output is correct |
35 |
Correct |
546 ms |
44952 KB |
Output is correct |
36 |
Correct |
548 ms |
45052 KB |
Output is correct |