# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
549169 |
2022-04-15T10:50:18 Z |
krit3379 |
Valley (BOI19_valley) |
C++17 |
|
200 ms |
43832 KB |
#include<bits/stdc++.h>
using namespace std;
#define N 100005
int tin[N],tout[N],depp[N],bp[20][N],t;
long long dp[N],dep[N],mi[20][N],ans;
pair<int,int> edge[N];
vector<pair<int,long long>> g[N];
// dp[i] lowest shop in i subtree
void dfs(int s,int f){
tin[s]=++t;
if(dp[s]==-1)dp[s]=dep[s];
for(auto [x,w]:g[s]){
if(x==f)continue;
dep[x]=dep[s]+w;
dfs(x,s);
dp[s]=min(dp[s],dp[x]);
}
tout[s]=t;
}
void dfs2(int s,int f){
depp[s]=depp[f]+1;
bp[0][s]=f;
mi[0][s]=dp[f]-2*dep[f];
for(auto [x,w]:g[s]){
if(x==f)continue;
dfs2(x,s);
}
}
int main(){
int n,s,q,e,a,b,i,j,k,idx,r;
long long w;
scanf("%d %d %d %d",&n,&s,&q,&e);
for(i=1;i<n;i++){
scanf("%d %d %lld",&a,&b,&w);
g[a].push_back({b,w});
g[b].push_back({a,w});
edge[i]={a,b};
dp[i]=1e18;
}
dp[n]=1e18;
for(i=1;i<=s;i++){
scanf("%d",&k);
dp[k]=-1;
}
dfs(e,0);
dfs2(e,0);
for(i=1;i<20;i++)for(j=1;j<=n;j++)bp[i][j]=bp[i-1][bp[i-1][j]],mi[i][j]=min(mi[i-1][j],mi[i-1][bp[i-1][j]]);
while(q--){
scanf("%d %d",&idx,&r);
auto [a,b]=edge[idx];
a=(depp[a]>depp[b])?a:b;
if(tin[a]<=tin[r]&&tin[r]<=tout[a]){
int dif=depp[r]-depp[a],temp=r;
ans=dp[r]-dep[r];
for(i=0;i<20;i++)if(dif&(1<<i))ans=min(ans,dep[r]+mi[i][temp]),temp=bp[i][temp];
if(ans>1e16)printf("oo\n");
else printf("%lld\n",ans);
}
else printf("escaped\n");
}
return 0;
}
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | scanf("%d %d %d %d",&n,&s,&q,&e);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | scanf("%d %d %lld",&a,&b,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d",&k);
| ~~~~~^~~~~~~~~
valley.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf("%d %d",&idx,&r);
| ~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3056 KB |
Output is correct |
2 |
Correct |
6 ms |
3008 KB |
Output is correct |
3 |
Correct |
5 ms |
3028 KB |
Output is correct |
4 |
Correct |
6 ms |
3076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3056 KB |
Output is correct |
2 |
Correct |
6 ms |
3008 KB |
Output is correct |
3 |
Correct |
5 ms |
3028 KB |
Output is correct |
4 |
Correct |
6 ms |
3076 KB |
Output is correct |
5 |
Correct |
2 ms |
3156 KB |
Output is correct |
6 |
Correct |
3 ms |
3156 KB |
Output is correct |
7 |
Correct |
3 ms |
3156 KB |
Output is correct |
8 |
Correct |
2 ms |
3156 KB |
Output is correct |
9 |
Correct |
3 ms |
3156 KB |
Output is correct |
10 |
Correct |
3 ms |
3156 KB |
Output is correct |
11 |
Correct |
3 ms |
3128 KB |
Output is correct |
12 |
Correct |
3 ms |
3156 KB |
Output is correct |
13 |
Correct |
3 ms |
3156 KB |
Output is correct |
14 |
Correct |
3 ms |
3156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
173 ms |
39188 KB |
Output is correct |
2 |
Correct |
131 ms |
39040 KB |
Output is correct |
3 |
Correct |
147 ms |
39244 KB |
Output is correct |
4 |
Correct |
157 ms |
41208 KB |
Output is correct |
5 |
Correct |
175 ms |
41316 KB |
Output is correct |
6 |
Correct |
175 ms |
43344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3056 KB |
Output is correct |
2 |
Correct |
6 ms |
3008 KB |
Output is correct |
3 |
Correct |
5 ms |
3028 KB |
Output is correct |
4 |
Correct |
6 ms |
3076 KB |
Output is correct |
5 |
Correct |
2 ms |
3156 KB |
Output is correct |
6 |
Correct |
3 ms |
3156 KB |
Output is correct |
7 |
Correct |
3 ms |
3156 KB |
Output is correct |
8 |
Correct |
2 ms |
3156 KB |
Output is correct |
9 |
Correct |
3 ms |
3156 KB |
Output is correct |
10 |
Correct |
3 ms |
3156 KB |
Output is correct |
11 |
Correct |
3 ms |
3128 KB |
Output is correct |
12 |
Correct |
3 ms |
3156 KB |
Output is correct |
13 |
Correct |
3 ms |
3156 KB |
Output is correct |
14 |
Correct |
3 ms |
3156 KB |
Output is correct |
15 |
Correct |
173 ms |
39188 KB |
Output is correct |
16 |
Correct |
131 ms |
39040 KB |
Output is correct |
17 |
Correct |
147 ms |
39244 KB |
Output is correct |
18 |
Correct |
157 ms |
41208 KB |
Output is correct |
19 |
Correct |
175 ms |
41316 KB |
Output is correct |
20 |
Correct |
175 ms |
43344 KB |
Output is correct |
21 |
Correct |
110 ms |
38772 KB |
Output is correct |
22 |
Correct |
180 ms |
38536 KB |
Output is correct |
23 |
Correct |
129 ms |
38808 KB |
Output is correct |
24 |
Correct |
151 ms |
40860 KB |
Output is correct |
25 |
Correct |
200 ms |
43832 KB |
Output is correct |
26 |
Correct |
107 ms |
38768 KB |
Output is correct |
27 |
Correct |
136 ms |
38604 KB |
Output is correct |
28 |
Correct |
151 ms |
38780 KB |
Output is correct |
29 |
Correct |
150 ms |
40204 KB |
Output is correct |
30 |
Correct |
169 ms |
41900 KB |
Output is correct |
31 |
Correct |
129 ms |
38732 KB |
Output is correct |
32 |
Correct |
126 ms |
38604 KB |
Output is correct |
33 |
Correct |
130 ms |
38888 KB |
Output is correct |
34 |
Correct |
180 ms |
40800 KB |
Output is correct |
35 |
Correct |
156 ms |
43744 KB |
Output is correct |
36 |
Correct |
141 ms |
40744 KB |
Output is correct |