oj.uz

Submission #689962

# Submission time Handle Problem Language Result Execution time Memory
689962 2023-01-29T22:10:47 Z EthanKim8683 Valley (BOI19_valley) C++17
100 / 100
 186 ms 59448 KB 
#include<bits/stdc++.h>
using namespace std;
using I=int;
using B=bool;
using Lli=long long int;
const I N=100000;
const I LOGN=17;
const I S=N;
const I W=1e9;
const Lli MAX=1e18;
vector<pair<I,I>>adjs[N];
I w_arr[N-1];
I c_arr[S];
B shps[N];
Lli lows[N];
Lli diss[N];
I deps[N];
tuple<I,Lli,B>ancs[N][LOGN];
I bots[N-1];
I tbgs[N],teds[N];
I t=0;
void dfs(I a,I p,Lli dis=0,I dep=0){
  tbgs[a]=t++;
  lows[a]=shps[a]?0:MAX;
  diss[a]=dis,deps[a]=dep;
  for(auto[b,i]:adjs[a])if(b!=p){
    I w=w_arr[i];
    bots[i]=b;
    dfs(b,a,dis+w,dep+1);
    lows[a]=min(lows[a],lows[b]+w);
    shps[a]|=shps[b];
  }
  for(auto[b,w]:adjs[a])if(b!=p)ancs[b][0]={a,dis-lows[a],shps[a]};
  teds[a]=t;
}
Lli qry(I i,I j){
  Lli upp=diss[i],res=diss[i]-lows[i];B vld=shps[i];
  for(I k=0;k<LOGN;k++)if(j>>k&1){
    auto[l,d,f]=ancs[i][k];
    i=l,res=max(res,d),vld|=f;
  }
  return vld?upp-res:-1;
}
B anc(I a,I b){
  return tbgs[a]<=tbgs[b]&&teds[a]>=teds[b];
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I n,s,q,e;cin>>n>>s>>q>>e,e--;
  for(I i=0;i<n-1;i++){
    I a,b,w;cin>>a>>b>>w,a--,b--;
    adjs[a].push_back({b,i});
    adjs[b].push_back({a,i});
    w_arr[i]=w;
  }
  for(I i=0;i<s;i++){I c;cin>>c,c_arr[i]=c-1;}
  for(I i=0;i<s;i++)shps[c_arr[i]]=1;
  dfs(e,e);
  ancs[e][0]={e,0-lows[e],shps[e]};
  for(I i=1;i<LOGN;i++)for(I j=0;j<n;j++){
    auto[k,d1,f1]=ancs[j][i-1];auto[l,d2,f2]=ancs[k][i-1];
    ancs[j][i]={l,max(d1,d2),f1|f2};
  }
  while(q--){
    I i,r;cin>>i>>r,i--,r--;
    I j=bots[i];
    if(!anc(j,r)){printf("escaped\n");continue;}
    Lli d=qry(r,deps[r]-deps[j]);
    d==-1?printf("oo\n"):printf("%lli\n",d);
  }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 4 ms 2892 KB Output is correct
3 Correct 3 ms 2816 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 4 ms 2892 KB Output is correct
3 Correct 3 ms 2816 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct
5 Correct 2 ms 3200 KB Output is correct
6 Correct 2 ms 3192 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Correct 3 ms 3204 KB Output is correct
10 Correct 3 ms 3156 KB Output is correct
11 Correct 2 ms 3232 KB Output is correct
12 Correct 3 ms 3120 KB Output is correct
13 Correct 2 ms 3196 KB Output is correct
14 Correct 4 ms 3248 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 51152 KB Output is correct
2 Correct 141 ms 50752 KB Output is correct
3 Correct 138 ms 50748 KB Output is correct
4 Correct 158 ms 52836 KB Output is correct
5 Correct 138 ms 52916 KB Output is correct
6 Correct 171 ms 55284 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 4 ms 2892 KB Output is correct
3 Correct 3 ms 2816 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct
5 Correct 2 ms 3200 KB Output is correct
6 Correct 2 ms 3192 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Correct 3 ms 3204 KB Output is correct
10 Correct 3 ms 3156 KB Output is correct
11 Correct 2 ms 3232 KB Output is correct
12 Correct 3 ms 3120 KB Output is correct
13 Correct 2 ms 3196 KB Output is correct
14 Correct 4 ms 3248 KB Output is correct
15 Correct 130 ms 51152 KB Output is correct
16 Correct 141 ms 50752 KB Output is correct
17 Correct 138 ms 50748 KB Output is correct
18 Correct 158 ms 52836 KB Output is correct
19 Correct 138 ms 52916 KB Output is correct
20 Correct 171 ms 55284 KB Output is correct
21 Correct 130 ms 54108 KB Output is correct
22 Correct 128 ms 53736 KB Output is correct
23 Correct 143 ms 53576 KB Output is correct
24 Correct 167 ms 56168 KB Output is correct
25 Correct 185 ms 59448 KB Output is correct
26 Correct 127 ms 54032 KB Output is correct
27 Correct 133 ms 53788 KB Output is correct
28 Correct 154 ms 53628 KB Output is correct
29 Correct 145 ms 55336 KB Output is correct
30 Correct 168 ms 56940 KB Output is correct
31 Correct 139 ms 54144 KB Output is correct
32 Correct 128 ms 53796 KB Output is correct
33 Correct 132 ms 53812 KB Output is correct
34 Correct 186 ms 56088 KB Output is correct
35 Correct 155 ms 59344 KB Output is correct
36 Correct 136 ms 56252 KB Output is correct