# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
876582 |
2023-11-22T02:18:12 Z |
imarn |
Valley (BOI19_valley) |
C++14 |
|
170 ms |
50516 KB |
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define f first
#define s second
#define vi vector<int>
#define vll vector<long long>
#define vpii vector<pii>
using namespace std;
const int N=1e5+5;
vector<pii>g[N];
ll d[N]{0},pr[N][18],dp[N][19],dep[N]{0},node[N]{0};
pii ro[N];
int tin[N]{0},tout[N]{0};
int t=0;
ll dfs(int u,int p,int l){
pr[u][0]=p;dep[u]=l;ll mn=1e17;
for(int i=1;i<=17;i++)pr[u][i]=pr[pr[u][i-1]][i-1];
if(node[u])mn=d[u];
tin[u]=++t;
for(auto v:g[u]){
if(v.f==p)continue;
d[v.f]=d[u]+v.s;
mn=min(mn,dfs(v.f,u,l+1));
}dp[u][0] = mn-2*d[u];tout[u]=t;
return mn;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,s,q,e;cin>>n>>s>>q>>e;
for(int i=1,u,v,w;i<=n-1;i++)cin>>u>>v>>w,g[u].pb({v,w}),g[v].pb({u,w}),ro[i]={u,v};
for(int i=1,u;i<=s;i++)cin>>u,node[u]=1;
dfs(e,e,0);
for(int j=1;j<=18;j++)for(int i=1;i<=n;i++)dp[i][j]=min(dp[i][j-1],dp[pr[i][j-1]][j-1]);
while(q--){
int i,r,x,y;cin>>i>>r;tie(x,y)=ro[i];if(dep[x]<dep[y])swap(x,y);ll ans=1e17;int cur=r;
if(!(tin[x]<=tin[r]&&tin[r]<=tout[x])){cout<<"escaped\n";continue;}
for(int i=17;i>=0;i--)if(dep[x]<=dep[pr[cur][i]])ans=min(ans,dp[cur][i]+d[r]),cur=pr[cur][i];
ans=min(ans,d[r]+dp[cur][0]);
if(ans>=1e15)cout<<"oo\n";
else cout<<ans<<"\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9564 KB |
Output is correct |
2 |
Correct |
4 ms |
9764 KB |
Output is correct |
3 |
Correct |
4 ms |
9716 KB |
Output is correct |
4 |
Correct |
3 ms |
9612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9564 KB |
Output is correct |
2 |
Correct |
4 ms |
9764 KB |
Output is correct |
3 |
Correct |
4 ms |
9716 KB |
Output is correct |
4 |
Correct |
3 ms |
9612 KB |
Output is correct |
5 |
Correct |
2 ms |
9712 KB |
Output is correct |
6 |
Correct |
3 ms |
9560 KB |
Output is correct |
7 |
Correct |
2 ms |
9564 KB |
Output is correct |
8 |
Correct |
2 ms |
9564 KB |
Output is correct |
9 |
Correct |
2 ms |
9612 KB |
Output is correct |
10 |
Correct |
3 ms |
9564 KB |
Output is correct |
11 |
Correct |
2 ms |
9680 KB |
Output is correct |
12 |
Correct |
2 ms |
9564 KB |
Output is correct |
13 |
Correct |
2 ms |
9608 KB |
Output is correct |
14 |
Correct |
2 ms |
9564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
119 ms |
42488 KB |
Output is correct |
2 |
Correct |
126 ms |
42064 KB |
Output is correct |
3 |
Correct |
126 ms |
42056 KB |
Output is correct |
4 |
Correct |
168 ms |
44184 KB |
Output is correct |
5 |
Correct |
140 ms |
44120 KB |
Output is correct |
6 |
Correct |
135 ms |
46300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9564 KB |
Output is correct |
2 |
Correct |
4 ms |
9764 KB |
Output is correct |
3 |
Correct |
4 ms |
9716 KB |
Output is correct |
4 |
Correct |
3 ms |
9612 KB |
Output is correct |
5 |
Correct |
2 ms |
9712 KB |
Output is correct |
6 |
Correct |
3 ms |
9560 KB |
Output is correct |
7 |
Correct |
2 ms |
9564 KB |
Output is correct |
8 |
Correct |
2 ms |
9564 KB |
Output is correct |
9 |
Correct |
2 ms |
9612 KB |
Output is correct |
10 |
Correct |
3 ms |
9564 KB |
Output is correct |
11 |
Correct |
2 ms |
9680 KB |
Output is correct |
12 |
Correct |
2 ms |
9564 KB |
Output is correct |
13 |
Correct |
2 ms |
9608 KB |
Output is correct |
14 |
Correct |
2 ms |
9564 KB |
Output is correct |
15 |
Correct |
119 ms |
42488 KB |
Output is correct |
16 |
Correct |
126 ms |
42064 KB |
Output is correct |
17 |
Correct |
126 ms |
42056 KB |
Output is correct |
18 |
Correct |
168 ms |
44184 KB |
Output is correct |
19 |
Correct |
140 ms |
44120 KB |
Output is correct |
20 |
Correct |
135 ms |
46300 KB |
Output is correct |
21 |
Correct |
115 ms |
45396 KB |
Output is correct |
22 |
Correct |
127 ms |
45140 KB |
Output is correct |
23 |
Correct |
123 ms |
45396 KB |
Output is correct |
24 |
Correct |
141 ms |
47508 KB |
Output is correct |
25 |
Correct |
150 ms |
50500 KB |
Output is correct |
26 |
Correct |
110 ms |
45392 KB |
Output is correct |
27 |
Correct |
120 ms |
45324 KB |
Output is correct |
28 |
Correct |
140 ms |
45612 KB |
Output is correct |
29 |
Correct |
150 ms |
46928 KB |
Output is correct |
30 |
Correct |
170 ms |
48568 KB |
Output is correct |
31 |
Correct |
107 ms |
45644 KB |
Output is correct |
32 |
Correct |
132 ms |
45788 KB |
Output is correct |
33 |
Correct |
131 ms |
45556 KB |
Output is correct |
34 |
Correct |
150 ms |
47596 KB |
Output is correct |
35 |
Correct |
144 ms |
50516 KB |
Output is correct |
36 |
Correct |
136 ms |
47488 KB |
Output is correct |