Submission #924478

#	Time	Username	Problem	Language	Result	Execution time	Memory
924478		UmairAhmadMirza	Toll (BOI17_toll)	C++17	100 / 100	177 ms	25680 KiB

toll

#include <bits/stdc++.h>
using namespace std;
int const N=2e5;
int const inf=1e9+5;
int wei[N][20][6];
int main(){
  int k,n,m,o;
  cin>>k>>n>>m>>o;
  for(int i=0;i<n;i++)
    for(int j=0;j<=16;j++)
      for(int kk=0;kk<=5;kk++)
        wei[i][j][kk]=inf;
  for(int i=0;i<m;i++){
    int a,b,w;
    cin>>a>>b>>w;
    // swap(a,b);//switch directions;
    wei[a][0][b%k]=w;
  }
  //compute
  int midnode=0;
  for(int par=1;par<=15;par++){
    for(int node=0;node<n;node++){
      midnode=(((1<<(par-1))+(node/k))*k);
      for(int md=0;md<k;md++){
        for(int d=0;d<k;d++){
          wei[node][par][md]=min(wei[node][par][md],(wei[node][par-1][d]+wei[midnode+d][par-1][md]));
        }
      }
    }
  }
  while(o--){
    int a,b;
    cin>>a>>b;
    int d=(b/k)-(a/k);
    if(d<0){
      cout<<-1<<endl;
      continue;
    }
    int w[k],ww[k];
    for(int i=0;i<k;i++)
      w[i]=inf;
    w[a%k]=0;
    int cur=a/k;
    while(d){
      int par=31-(__builtin_clz(d));
      d-=(1<<par);
      // cout<<"par "<<par<<endl;
      for(int i=0;i<k;i++){
        int mn=inf;
        for(int j=0;j<k;j++)
          mn=min(mn,w[j]+wei[(cur*k)+j][par][i]);
        ww[i]=mn;
      }
      for(int i=0;i<k;i++)
        w[i]=ww[i];
      cur+=(1<<par);
    }
    if(w[b%k]>=inf)
      w[b%k]=-1;
    cout<<w[b%k]<<endl;
  }
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44