Submission #689975

#	Time	Username	Problem	Language	Result	Execution time	Memory
689975		EthanKim8683	Toll (BOI17_toll)	C++17	100 / 100	162 ms	36104 KiB

toll

#include<bits/stdc++.h>
using namespace std;
using I=int;
using B=bool;
const I N=50000;
const I K=5;
const I LOGN=16;
const I MAX=1e9;
vector<I>adjs[N];
pair<I,I>ancs[N][LOGN][K];
pair<I,I>tmps[2][K];
I main(){
  cin.tie(0)->sync_with_stdio(0);
  fill(&ancs[0][0][0],&ancs[0][0][0]+N*LOGN*K,pair<I,I>{MAX,-1});
  I k,n,m,o;cin>>k>>n>>m>>o;
  for(I i=0;i<m;i++){
    I a,b,t;cin>>a>>b>>t;
    ancs[a][0][b%k]={t,b};
  }
  for(I i=1;i<LOGN;i++)for(I j=0;j<n;j++){
    for(I x=0;x<k;x++){
      auto[d1,a]=ancs[j][i-1][x];
      if(a==-1)continue;
      for(I y=0;y<k;y++){
        auto[d2,b]=ancs[a][i-1][y];
        if(b==-1)continue;
        ancs[j][i][y]=min(ancs[j][i][y],{d1+d2,b});
      }
    }
  }
  while(o--){
    I a,b;cin>>a>>b;
    I cnt=b/k-a/k,t=0;
    fill_n(tmps[t],k,pair<I,I>{MAX,-1});
    tmps[t][a%k]={0,a};
    for(I i=0;i<LOGN;i++)if(cnt>>i&1){
      fill_n(tmps[!t],k,pair<I,I>{MAX,-1});
      for(I x=0;x<k;x++){
        auto[d1,a]=tmps[t][x];
        if(a==-1)continue;
        for(I y=0;y<k;y++){
          auto[d2,b]=ancs[a][i][y];
          if(b==-1)continue;
          tmps[!t][y]=min(tmps[!t][y],{d1+d2,b});
        }
      }
      t=!t;
    }
    auto[d,c]=tmps[t][b%k];
    printf("%i\n",c==-1?-1:d);
  }
}

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