# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
720146 |
2023-04-07T13:51:37 Z |
Ahmed57 |
Valley (BOI19_valley) |
C++14 |
|
482 ms |
57360 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
long long dis[100001];
bool ch[100001];
long long an[100001];
vector<pair<int,long long>> adj[100001];
int P[100001][17];
pair<long long,long long> V[100001][17];int dep[100001];
void dfs(int i,int pr){
P[i][0] = pr;
dep[i] = dep[pr]+1;
V[i][0] = {an[i]-dis[i],dis[i]};
for(int j = 1;j<17;j++){
P[i][j] = P[P[i][j-1]][j-1];
V[i][j] = min(V[i][j-1],V[P[i][j-1]][j-1]);
}
for(auto j:adj[i]){
if(j.first==pr)continue;
dis[j.first] = dis[i]+j.second;
dfs(j.first,i);
}
}
long long calc(int i,int pr){
long long ans = (ch[i]?0:1e18);
for(auto j:adj[i]){
if(j.first==pr)continue;
ans = min(ans,calc(j.first,i)+j.second);
}
return an[i] = ans;
}
bool can(int no1,int no2){
if(dep[no1]<dep[no2])return 0;
for(int j = 16;j>=0;j--){
if(dep[no1]-dep[no2]>=(1<<j)){
no1=P[no1][j];
}
}
return no1==no2;
}
pair<long long,long long> lca(long long no1,long long no2){
pair<long long,long long> ans = {1e18,0};
for(int j = 16;j>=0;j--){
if(dep[no1]-dep[no2]+1>=(1<<j)){
ans = min(ans,V[no1][j]);
no1=P[no1][j];
}
}
return ans;
}
signed main(){
an[0]= 1e18;
int n,s,q,e;
cin>>n>>s>>q>>e;
vector<pair<long long,long long>> v;
for(int i = 0;i<n-1;i++){
long long a,b,c;cin>>a>>b>>c;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
v.push_back({a,b});
}
for(int i = 0;i<s;i++){
int x;cin>>x;ch[x] = 1;
}
calc(e,1);
dfs(e,1);
for(int i = 0;i<v.size();i++){
if(dep[v[i].first]>dep[v[i].second])swap(v[i].first,v[i].second);
}
while(q--){
int blo,nod;cin>>blo>>nod;
blo = v[blo-1].second;
if(can(nod,blo)){
pair<long long,long long> val = lca(nod,blo);
if(val.first>=1e16){
cout<<"oo"<<endl;
}else{
cout<<val.first+val.second+(dis[nod]-val.second)<<endl;
}
}else cout<<"escaped"<<endl;
}
}
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:68:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 0;i<v.size();i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
2784 KB |
Output is correct |
2 |
Correct |
17 ms |
2856 KB |
Output is correct |
3 |
Correct |
19 ms |
2860 KB |
Output is correct |
4 |
Correct |
18 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
2784 KB |
Output is correct |
2 |
Correct |
17 ms |
2856 KB |
Output is correct |
3 |
Correct |
19 ms |
2860 KB |
Output is correct |
4 |
Correct |
18 ms |
2772 KB |
Output is correct |
5 |
Correct |
5 ms |
3156 KB |
Output is correct |
6 |
Correct |
5 ms |
3156 KB |
Output is correct |
7 |
Correct |
5 ms |
3196 KB |
Output is correct |
8 |
Correct |
5 ms |
3156 KB |
Output is correct |
9 |
Correct |
5 ms |
3156 KB |
Output is correct |
10 |
Correct |
5 ms |
3156 KB |
Output is correct |
11 |
Correct |
6 ms |
3128 KB |
Output is correct |
12 |
Correct |
5 ms |
3192 KB |
Output is correct |
13 |
Correct |
4 ms |
3192 KB |
Output is correct |
14 |
Correct |
4 ms |
3188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
403 ms |
52360 KB |
Output is correct |
2 |
Correct |
434 ms |
52160 KB |
Output is correct |
3 |
Correct |
420 ms |
52360 KB |
Output is correct |
4 |
Correct |
480 ms |
53900 KB |
Output is correct |
5 |
Correct |
454 ms |
54072 KB |
Output is correct |
6 |
Correct |
452 ms |
55672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
2784 KB |
Output is correct |
2 |
Correct |
17 ms |
2856 KB |
Output is correct |
3 |
Correct |
19 ms |
2860 KB |
Output is correct |
4 |
Correct |
18 ms |
2772 KB |
Output is correct |
5 |
Correct |
5 ms |
3156 KB |
Output is correct |
6 |
Correct |
5 ms |
3156 KB |
Output is correct |
7 |
Correct |
5 ms |
3196 KB |
Output is correct |
8 |
Correct |
5 ms |
3156 KB |
Output is correct |
9 |
Correct |
5 ms |
3156 KB |
Output is correct |
10 |
Correct |
5 ms |
3156 KB |
Output is correct |
11 |
Correct |
6 ms |
3128 KB |
Output is correct |
12 |
Correct |
5 ms |
3192 KB |
Output is correct |
13 |
Correct |
4 ms |
3192 KB |
Output is correct |
14 |
Correct |
4 ms |
3188 KB |
Output is correct |
15 |
Correct |
403 ms |
52360 KB |
Output is correct |
16 |
Correct |
434 ms |
52160 KB |
Output is correct |
17 |
Correct |
420 ms |
52360 KB |
Output is correct |
18 |
Correct |
480 ms |
53900 KB |
Output is correct |
19 |
Correct |
454 ms |
54072 KB |
Output is correct |
20 |
Correct |
452 ms |
55672 KB |
Output is correct |
21 |
Correct |
401 ms |
53108 KB |
Output is correct |
22 |
Correct |
400 ms |
52912 KB |
Output is correct |
23 |
Correct |
411 ms |
53044 KB |
Output is correct |
24 |
Correct |
444 ms |
54852 KB |
Output is correct |
25 |
Correct |
465 ms |
57360 KB |
Output is correct |
26 |
Correct |
347 ms |
53132 KB |
Output is correct |
27 |
Correct |
376 ms |
53004 KB |
Output is correct |
28 |
Correct |
461 ms |
53352 KB |
Output is correct |
29 |
Correct |
416 ms |
54420 KB |
Output is correct |
30 |
Correct |
466 ms |
55864 KB |
Output is correct |
31 |
Correct |
398 ms |
53276 KB |
Output is correct |
32 |
Correct |
372 ms |
53068 KB |
Output is correct |
33 |
Correct |
396 ms |
53276 KB |
Output is correct |
34 |
Correct |
439 ms |
54800 KB |
Output is correct |
35 |
Correct |
482 ms |
57256 KB |
Output is correct |
36 |
Correct |
425 ms |
55416 KB |
Output is correct |