# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
556693 |
2022-05-03T17:03:03 Z |
jasmin |
Valley (BOI19_valley) |
C++14 |
|
315 ms |
65236 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
int l=25;
const int inf=1e18;
struct graph{
vector<pair<int,int> > edge;
vector<vector<pair<int,int> > >adi;
vector<bool> shop;
vector<int> tin;
vector<int> tout;
vector<int> dist;
vector<int> down;
int t=0;
vector<vector<int> > up;
vector<vector<int> > best;
graph(int n){
edge.resize(n-1);
adi.resize(n);
shop.resize(n);
tin.resize(n);
tout.resize(n);
dist.resize(n);
down.resize(n, inf);
up.resize(n, vector<int> (l, -1));
best.resize(n, vector<int> (l, inf));
}
void dfs1(int v, int p){
tin[v]=t; t++;
if(shop[v]){
down[v]=0;
}
for(auto u: adi[v]){
if(u.first!=p){
dist[u.first]=dist[v]+u.second;
dfs1(u.first, v);
down[v]=min(down[v], down[u.first]+u.second);
}
}
tout[v]=t; t++;
}
void dfs2(int v, int p, int d){
up[v][0]=p;
if(p!=-1){
best[v][0]=min(down[v], down[p]+d);
}
for(int i=1; i<l; i++){
if(up[v][i-1]==-1) break;
up[v][i]=up[up[v][i-1]][i-1];
best[v][i]=min(best[v][i-1], best[up[v][i-1]][i-1]+(dist[v]-dist[up[v][i-1]]));
}
for(auto u: adi[v]){
if(u.first!=p){
dfs2(u.first, v, u.second);
}
}
}
bool is_ancestor(int a, int b){
return tin[a]<=tin[b] && tout[b]<=tout[a];
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, s, q, e;
cin >> n >> s >> q >> e;
e--;
graph g(n);
for(int i=0; i<n-1; i++){
int a, b, c;
cin >> a >> b >> c;
a--; b--;
g.edge[i]={a, b};
g.adi[a].push_back({b, c});
g.adi[b].push_back({a, c});
}
for(int i=0; i<s; i++){
int a;
cin >> a;
a--;
g.shop[a]=true;
}
g.dfs1(e, -1);
g.dfs2(e, -1, 0);
for(int i=0; i<q; i++){
int x, r;
cin >> x >> r;
x--; r--;
if(g.is_ancestor(g.edge[x].second, g.edge[x].first)){
swap(g.edge[x].first, g.edge[x].second);
}
//cout << g.edge[x].second << " " << r << "\n";
if(!g.is_ancestor(g.edge[x].second, r)){
cout << "escaped\n";
continue;
}
int h=g.tin[g.edge[x].first];
int ans=g.down[r];
int a=0;
for(int j=l-1; j>=0; j--){
if(g.up[r][j]==-1) continue;
//cout << r << " " << j << " " << g.up[r][j] << " " << g.tin[g.up[r][j]] << " " << h << "\n";
if(h<g.tin[g.up[r][j]]){
//cout << "=> " << g.best[r][j] << " " << a << "\n";
ans=min(ans, g.best[r][j]+a);
a+=g.dist[r]-g.dist[g.up[r][j]];
r=g.up[r][j];
}
}
if(ans==inf){
cout << "oo\n";
}
else{
cout << ans << "\n";
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
460 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
2 ms |
852 KB |
Output is correct |
8 |
Correct |
3 ms |
852 KB |
Output is correct |
9 |
Correct |
2 ms |
844 KB |
Output is correct |
10 |
Correct |
1 ms |
852 KB |
Output is correct |
11 |
Correct |
3 ms |
844 KB |
Output is correct |
12 |
Correct |
2 ms |
852 KB |
Output is correct |
13 |
Correct |
2 ms |
852 KB |
Output is correct |
14 |
Correct |
2 ms |
904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
154 ms |
58480 KB |
Output is correct |
2 |
Correct |
205 ms |
62156 KB |
Output is correct |
3 |
Correct |
203 ms |
62536 KB |
Output is correct |
4 |
Correct |
269 ms |
63548 KB |
Output is correct |
5 |
Correct |
230 ms |
63780 KB |
Output is correct |
6 |
Correct |
294 ms |
64924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
460 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
2 ms |
852 KB |
Output is correct |
8 |
Correct |
3 ms |
852 KB |
Output is correct |
9 |
Correct |
2 ms |
844 KB |
Output is correct |
10 |
Correct |
1 ms |
852 KB |
Output is correct |
11 |
Correct |
3 ms |
844 KB |
Output is correct |
12 |
Correct |
2 ms |
852 KB |
Output is correct |
13 |
Correct |
2 ms |
852 KB |
Output is correct |
14 |
Correct |
2 ms |
904 KB |
Output is correct |
15 |
Correct |
154 ms |
58480 KB |
Output is correct |
16 |
Correct |
205 ms |
62156 KB |
Output is correct |
17 |
Correct |
203 ms |
62536 KB |
Output is correct |
18 |
Correct |
269 ms |
63548 KB |
Output is correct |
19 |
Correct |
230 ms |
63780 KB |
Output is correct |
20 |
Correct |
294 ms |
64924 KB |
Output is correct |
21 |
Correct |
163 ms |
61860 KB |
Output is correct |
22 |
Correct |
199 ms |
61612 KB |
Output is correct |
23 |
Correct |
188 ms |
61808 KB |
Output is correct |
24 |
Correct |
263 ms |
63304 KB |
Output is correct |
25 |
Correct |
273 ms |
65236 KB |
Output is correct |
26 |
Correct |
160 ms |
61888 KB |
Output is correct |
27 |
Correct |
187 ms |
61792 KB |
Output is correct |
28 |
Correct |
227 ms |
62028 KB |
Output is correct |
29 |
Correct |
240 ms |
62956 KB |
Output is correct |
30 |
Correct |
315 ms |
63960 KB |
Output is correct |
31 |
Correct |
161 ms |
61952 KB |
Output is correct |
32 |
Correct |
171 ms |
61736 KB |
Output is correct |
33 |
Correct |
192 ms |
62088 KB |
Output is correct |
34 |
Correct |
284 ms |
63332 KB |
Output is correct |
35 |
Correct |
275 ms |
65064 KB |
Output is correct |
36 |
Correct |
231 ms |
63144 KB |
Output is correct |