# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
898550 |
2024-01-04T21:31:09 Z |
Mathias |
Valley (BOI19_valley) |
C++14 |
|
147 ms |
49452 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18;
const ll MAXN = 1e5+7;
const ll LOG = 18;
struct str{
ll fi,sc;
};
int pre[MAXN];
int post[MAXN];
ll wo[MAXN];
int depth[MAXN];
int degree[MAXN];
int ojciec[MAXN];
ll dis[MAXN];
ll suma[MAXN];
bool visited[MAXN];
str jp[MAXN][LOG];
pair<int,int> in[MAXN];
vector<pair<int,ll> > g[MAXN];
queue<int> que;
ll w,diff,cnt=0;
void DFS(int x,int f,ll d){
pre[x]=++cnt;
depth[x]=depth[f]+1;
suma[x]=suma[f]+d;
jp[x][0]={f,min(dis[f]+wo[x],dis[x])};
//cout<<jp[x][0].sc<<'\n';
for(ll i=1;i<LOG;i++){
jp[x][i].fi=jp[jp[x][i-1].fi][i-1].fi;
jp[x][i].sc=min(jp[x][i-1].sc,jp[jp[x][i-1].fi][i-1].sc-suma[jp[x][i-1].fi]+suma[x]);
//cout<<x<<' '<<i<<' '<<jp[x][i-1].sc<<' '<<jp[jp[x][i-1].fi][i-1].sc<<' '<<suma[jp[x][i-1].fi]<<' '<<suma[x]<<' '<<jp[x][i].sc<<'\n';
}
for(auto sas:g[x]){
if(f==sas.first) continue;
DFS(sas.first, x, sas.second);
}
post[x]=++cnt;
}
bool anc(int a,int b){
return (pre[a] <= pre[b] && post[a] >= post[b]);
}
void DFS1(int x,int f){
visited[x]=1;
ojciec[x]=f;
for(ll i=0;i<g[x].size();i++){
if(g[x][i].first==f) wo[x]=g[x][i].second;
if(!visited[g[x][i].first]){
DFS1(g[x][i].first, x);
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n,q,s,r,sk,a,b,x,y,b1,res=INF,c;
cin>>n>>s>>q>>r;
for(int i=1;i<n;i++){
cin>>a>>b>>c;
in[i]={a,b};
g[a].push_back({b,c});
g[b].push_back({a,c});
degree[a]++;
degree[b]++;
}
for(ll i=1;i<=n;i++){
if(degree[i]==1 and i!=r) que.push(i);
dis[i]=INF;
}
for(ll i=1;i<=s;i++){
cin>>sk;
dis[sk]=0;
}
for(ll i=1;i<=n;i++) visited[i]=0;
DFS1(r,0);
while(!que.empty()){
x=que.front();
que.pop();
dis[ojciec[x]]=min(dis[ojciec[x]], dis[x]+wo[x]);
degree[ojciec[x]]--;
if(degree[ojciec[x]]<=1 and ojciec[x]!=0) que.push(ojciec[x]);
}
DFS(r,r,0);
while(q--){
cin>>a>>b;
x=in[a].first;
y=in[a].second;
if(depth[x]>depth[y]) swap(x,y);
if(anc(y,b)==false){
cout<<"escaped\n";
continue;
}
res=dis[b];
b1=b;
for(int i=LOG-1;i>=0;i--){
if(depth[jp[b][i].fi]<depth[y]) continue;
if(jp[b][i].sc-suma[b]+suma[b1]<res){
res=jp[b][i].sc-suma[b]+suma[b1];
}
//cout<<b<<' '<<mini<<'\n';
b=jp[b][i].fi;
}
if(res==INF) cout<<"oo\n";
else cout<<res<<'\n';
}
return 0;
}
Compilation message
valley.cpp: In function 'void DFS1(int, int)':
valley.cpp:47:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(ll i=0;i<g[x].size();i++){
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8796 KB |
Output is correct |
2 |
Correct |
3 ms |
8796 KB |
Output is correct |
3 |
Correct |
3 ms |
8796 KB |
Output is correct |
4 |
Correct |
3 ms |
8796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8796 KB |
Output is correct |
2 |
Correct |
3 ms |
8796 KB |
Output is correct |
3 |
Correct |
3 ms |
8796 KB |
Output is correct |
4 |
Correct |
3 ms |
8796 KB |
Output is correct |
5 |
Correct |
2 ms |
8924 KB |
Output is correct |
6 |
Correct |
2 ms |
8924 KB |
Output is correct |
7 |
Correct |
2 ms |
8796 KB |
Output is correct |
8 |
Correct |
2 ms |
8796 KB |
Output is correct |
9 |
Correct |
2 ms |
8796 KB |
Output is correct |
10 |
Correct |
2 ms |
8796 KB |
Output is correct |
11 |
Correct |
3 ms |
9048 KB |
Output is correct |
12 |
Correct |
2 ms |
8796 KB |
Output is correct |
13 |
Correct |
2 ms |
8796 KB |
Output is correct |
14 |
Correct |
2 ms |
8796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
109 ms |
45752 KB |
Output is correct |
2 |
Correct |
113 ms |
45392 KB |
Output is correct |
3 |
Correct |
118 ms |
45504 KB |
Output is correct |
4 |
Correct |
147 ms |
47068 KB |
Output is correct |
5 |
Correct |
120 ms |
47384 KB |
Output is correct |
6 |
Correct |
142 ms |
48724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8796 KB |
Output is correct |
2 |
Correct |
3 ms |
8796 KB |
Output is correct |
3 |
Correct |
3 ms |
8796 KB |
Output is correct |
4 |
Correct |
3 ms |
8796 KB |
Output is correct |
5 |
Correct |
2 ms |
8924 KB |
Output is correct |
6 |
Correct |
2 ms |
8924 KB |
Output is correct |
7 |
Correct |
2 ms |
8796 KB |
Output is correct |
8 |
Correct |
2 ms |
8796 KB |
Output is correct |
9 |
Correct |
2 ms |
8796 KB |
Output is correct |
10 |
Correct |
2 ms |
8796 KB |
Output is correct |
11 |
Correct |
3 ms |
9048 KB |
Output is correct |
12 |
Correct |
2 ms |
8796 KB |
Output is correct |
13 |
Correct |
2 ms |
8796 KB |
Output is correct |
14 |
Correct |
2 ms |
8796 KB |
Output is correct |
15 |
Correct |
109 ms |
45752 KB |
Output is correct |
16 |
Correct |
113 ms |
45392 KB |
Output is correct |
17 |
Correct |
118 ms |
45504 KB |
Output is correct |
18 |
Correct |
147 ms |
47068 KB |
Output is correct |
19 |
Correct |
120 ms |
47384 KB |
Output is correct |
20 |
Correct |
142 ms |
48724 KB |
Output is correct |
21 |
Correct |
101 ms |
45440 KB |
Output is correct |
22 |
Correct |
110 ms |
45476 KB |
Output is correct |
23 |
Correct |
107 ms |
45252 KB |
Output is correct |
24 |
Correct |
128 ms |
46968 KB |
Output is correct |
25 |
Correct |
138 ms |
49420 KB |
Output is correct |
26 |
Correct |
96 ms |
45384 KB |
Output is correct |
27 |
Correct |
104 ms |
45080 KB |
Output is correct |
28 |
Correct |
113 ms |
45396 KB |
Output is correct |
29 |
Correct |
125 ms |
46672 KB |
Output is correct |
30 |
Correct |
144 ms |
47824 KB |
Output is correct |
31 |
Correct |
93 ms |
45648 KB |
Output is correct |
32 |
Correct |
116 ms |
45396 KB |
Output is correct |
33 |
Correct |
114 ms |
45396 KB |
Output is correct |
34 |
Correct |
136 ms |
47076 KB |
Output is correct |
35 |
Correct |
130 ms |
49452 KB |
Output is correct |
36 |
Correct |
128 ms |
47036 KB |
Output is correct |