oj.uz

Submission #715059

# Submission time Handle Problem Language Result Execution time Memory
715059 2023-03-25T21:55:54 Z EthanKim8683 Toll (BOI17_toll) C++17
0 / 100
 153 ms 25312 KB 
#include<bits/stdc++.h>
using namespace std;
using I=int;
const I N=50000;
const I T=10000;
const I K=5;
const I MAX=1e9;
vector<pair<I,I>>incs[N],outs[N];
vector<I>diss[2*N][K];
priority_queue<pair<I,I>>ques;
I k,n;
void slv(I i=1,I l=0,I r=(n-1)/k){
  if(l>r)return;
  I m=l+(r-l)/2;
  for(I j=0;j<min(k,n-m*k);j++){
    I low=l*k,mid=m*k+j,upp=min((r+1)*k,n);
    auto add=[&](I a,I dis){
      if(dis>=diss[i][j][a])return;
      if(a<0||a>=upp-low)return;
      ques.push({-(diss[i][j][a]=dis),a});
    };
    diss[i][j].resize(upp-low);
    fill(diss[i][j].begin(),diss[i][j].end(),MAX);
    diss[i][j][mid-low]=0;
    ques.push({0,mid-low});
    while(ques.size()){
      auto[dis,a]=ques.top();ques.pop();
      if((dis=-dis)!=diss[i][j][a])continue;
      for(auto[b,t]:outs[a+low])add(b-low,dis+t);
    }
    ques.push({0,mid-low});
    while(ques.size()){
      auto[dis,a]=ques.top();ques.pop();
      if((dis=-dis)!=diss[i][j][a])continue;
      for(auto[b,t]:incs[a+low])add(b-low,dis+t);
    }
  }
  slv(i<<1,l,m-1),slv(i<<1|1,m+1,r);
}
I qry(I l1,I r1,I i=1,I l2=0,I r2=(n-1)/k){
  I m=l2+(r2-l2)/2;
  if(l1/k>m)return qry(l1,r1,i<<1,m+1,r2);
  if(r1/k<m)return qry(l1,r1,i<<1|1,l2,m-1);
  I res=MAX;
  for(I j=0;j<min(k,n-m*k);j++){
    I low=l2*k,upp=min((r2+1)*k,n);
    res=min(res,diss[i][j][l1-low]+diss[i][j][r1-low]);
  }
  return res==MAX?-1:res;
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I m,o;cin>>k>>n>>m>>o;
  for(I i=0;i<m;i++){
    I a,b,t;cin>>a>>b>>t;
    outs[a].push_back({b,t});
    incs[b].push_back({a,t});
  }
  slv();
  while(o--){
    I a,b;cin>>a>>b;
    printf("%i\n",qry(a,b));
  }
}

Compilation message

toll.cpp: In function 'I qry(I, I, I, I, I)':
toll.cpp:46:16: warning: unused variable 'upp' [-Wunused-variable]
   46 |     I low=l2*k,upp=min((r2+1)*k,n);
      |                ^~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 22500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 25312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 22500 KB Output isn't correct
2 Halted 0 ms 0 KB -