# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
522786 |
2022-02-05T19:28:11 Z |
fadi57 |
Valley (BOI19_valley) |
C++14 |
|
483 ms |
53636 KB |
#include<bits/stdc++.h>
using namespace std;
const int mx=2e5+9;
typedef long long ll;
const int mod=1000000007;
const long long inf=1e18+10;
const int SQ=450;
int shop[mx];
int tin[mx],tout[mx],depth[mx];
ll cost[mx],mn[20][mx],dp[20][mx],dist[mx];
int tim;
int n,s,q,e;
vector<pair<int,int>>adj[mx];
int u[mx],v[mx];
void dfs(int node,int par){
tin[node]=tim++;
if(shop[node]==1){
cost[node]=0;
}else{
cost[node]=inf;
}
for(auto it:adj[node]){
if(it.first==par){continue;}
depth[it.first]=depth[node]+1;
dist[it.first]=dist[node]+it.second;
dfs(it.first,node);
cost[node]=min(cost[node],cost[it.first]+it.second);
}
tout[node]=tim++;
}
void dfs2(int node,int par){
dp[0][node]=par;
mn[0][node]=cost[par]-dist[par];
for(int i=1;i<20;i++){
dp[i][node]=dp[i-1][dp[i-1][node]];
mn[i][node]=min(mn[i-1][node],mn[i-1][dp[i-1][node]]);
}
for(auto it:adj[node]){
if(it.first==par){continue;}
dfs2(it.first,node);
}
}
bool ok(int x,int y){
if(tin[x]<=tin[y]&&tout[y]<=tout[x]){
return 1;
}
return 0;
}
ll calc(int node,int x ){
ll costt=inf;
int z=x;
for(int i=19;i>=0;i--){
if(depth[dp[i][x]]>=depth[node]){
costt=min(costt,mn[i][x]);
x=dp[i][x];
}
}
return costt;
}
int main(){
cin>>n>>s>>q>>e;
cost[0]=inf;
for(int i=0;i<n-1;i++){
int a,b,w;
cin>>a>>b>>w;
u[i]=a;
v[i]=b;
adj[a].push_back({b,w});
adj[b].push_back({a,w});
}
for(int i=0;i<s;i++){
int x;
cin>>x;
shop[x]=1;
}
dfs(e,0);
dfs2(e,0);
while(q--){
int i,r;
cin>>i>>r;
i--;
int node=v[i];
if(dp[0][u[i]]==v[i]){
node=u[i];
}
if(!ok(node,r)){
cout<<"escaped";
}else{
ll ans=calc(node,r);
ans=min(ans+dist[r],cost[r]);
if(ans>=inf){cout<<"oo";}else{cout<<ans;}
//cout<<node<<" "<<ans;
}
cout<<"\n";
}
}
Compilation message
valley.cpp: In function 'll calc(int, int)':
valley.cpp:67:13: warning: unused variable 'z' [-Wunused-variable]
67 | int z=x;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
5324 KB |
Output is correct |
2 |
Correct |
23 ms |
5392 KB |
Output is correct |
3 |
Correct |
19 ms |
5452 KB |
Output is correct |
4 |
Correct |
25 ms |
5424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
5324 KB |
Output is correct |
2 |
Correct |
23 ms |
5392 KB |
Output is correct |
3 |
Correct |
19 ms |
5452 KB |
Output is correct |
4 |
Correct |
25 ms |
5424 KB |
Output is correct |
5 |
Correct |
5 ms |
5708 KB |
Output is correct |
6 |
Correct |
5 ms |
5652 KB |
Output is correct |
7 |
Correct |
5 ms |
5708 KB |
Output is correct |
8 |
Correct |
7 ms |
5708 KB |
Output is correct |
9 |
Correct |
6 ms |
5648 KB |
Output is correct |
10 |
Correct |
8 ms |
5748 KB |
Output is correct |
11 |
Correct |
5 ms |
5708 KB |
Output is correct |
12 |
Correct |
6 ms |
5708 KB |
Output is correct |
13 |
Correct |
7 ms |
5784 KB |
Output is correct |
14 |
Correct |
6 ms |
5656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
405 ms |
44992 KB |
Output is correct |
2 |
Correct |
404 ms |
44684 KB |
Output is correct |
3 |
Correct |
423 ms |
44616 KB |
Output is correct |
4 |
Correct |
434 ms |
46788 KB |
Output is correct |
5 |
Correct |
426 ms |
46784 KB |
Output is correct |
6 |
Correct |
468 ms |
49096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
5324 KB |
Output is correct |
2 |
Correct |
23 ms |
5392 KB |
Output is correct |
3 |
Correct |
19 ms |
5452 KB |
Output is correct |
4 |
Correct |
25 ms |
5424 KB |
Output is correct |
5 |
Correct |
5 ms |
5708 KB |
Output is correct |
6 |
Correct |
5 ms |
5652 KB |
Output is correct |
7 |
Correct |
5 ms |
5708 KB |
Output is correct |
8 |
Correct |
7 ms |
5708 KB |
Output is correct |
9 |
Correct |
6 ms |
5648 KB |
Output is correct |
10 |
Correct |
8 ms |
5748 KB |
Output is correct |
11 |
Correct |
5 ms |
5708 KB |
Output is correct |
12 |
Correct |
6 ms |
5708 KB |
Output is correct |
13 |
Correct |
7 ms |
5784 KB |
Output is correct |
14 |
Correct |
6 ms |
5656 KB |
Output is correct |
15 |
Correct |
405 ms |
44992 KB |
Output is correct |
16 |
Correct |
404 ms |
44684 KB |
Output is correct |
17 |
Correct |
423 ms |
44616 KB |
Output is correct |
18 |
Correct |
434 ms |
46788 KB |
Output is correct |
19 |
Correct |
426 ms |
46784 KB |
Output is correct |
20 |
Correct |
468 ms |
49096 KB |
Output is correct |
21 |
Correct |
421 ms |
47932 KB |
Output is correct |
22 |
Correct |
440 ms |
47580 KB |
Output is correct |
23 |
Correct |
416 ms |
47496 KB |
Output is correct |
24 |
Correct |
450 ms |
49924 KB |
Output is correct |
25 |
Correct |
483 ms |
53244 KB |
Output is correct |
26 |
Correct |
372 ms |
48192 KB |
Output is correct |
27 |
Correct |
382 ms |
47804 KB |
Output is correct |
28 |
Correct |
419 ms |
47780 KB |
Output is correct |
29 |
Correct |
472 ms |
49432 KB |
Output is correct |
30 |
Correct |
466 ms |
51116 KB |
Output is correct |
31 |
Correct |
371 ms |
48348 KB |
Output is correct |
32 |
Correct |
401 ms |
48164 KB |
Output is correct |
33 |
Correct |
475 ms |
48060 KB |
Output is correct |
34 |
Correct |
435 ms |
50200 KB |
Output is correct |
35 |
Correct |
467 ms |
53636 KB |
Output is correct |
36 |
Correct |
428 ms |
50452 KB |
Output is correct |