Submission #683385

#	Time	Username	Problem	Language	Result	Execution time	Memory
683385		MtSaka	Toll (BOI17_toll)	C++17	100 / 100	251 ms	14184 KiB

toll

#include<bits/stdc++.h>
using namespace std;
int k,n,m,o;
constexpr int inf=1000000000;
struct Mat{
  vector<vector<int>>a;
  Mat(){
    a.assign(k,vector<int>(k,inf));
  }
  Mat(const vector<vector<int>>&b):a(b){}
  friend Mat operator*(const Mat&a,const Mat&b){
    Mat c=Mat();
    for(int i=0;i<k;i++)for(int j=0;j<k;j++)for(int l=0;l<k;l++)c.a[i][j]=min(c.a[i][j],a.a[i][l]+b.a[l][j]);
    return c;
  }
  static const Mat e(){
    Mat c=Mat();
    for(int i=0;i<k;i++)c.a[i][i]=0;
    return c;
  }
};
struct segtree{
  private:
  int n;
  vector<Mat>seg;
  public:
  segtree(int n):n(n){seg.assign(2*n,Mat::e());}
  segtree(const vector<Mat>&v){
    n=v.size();
    seg.assign(2*n,Mat::e());
    for(int i=0;i<n;i++)seg[i+n]=v[i];
    for(int i=n-1;i>0;i--)seg[i]=seg[i<<1]*seg[i<<1|1];
  }
  Mat prod(int l,int r)const{
    Mat sml=Mat::e(),smr=Mat::e();
    for(l+=n,r+=n;l<r;l>>=1,r>>=1){
      if(l&1)sml=sml*seg[l++];
      if(r&1)smr=seg[--r]*smr;
    }
    return sml*smr;
  }
};
int main(){
  cin>>k>>n>>m>>o;
  vector<Mat>mat(n/k);
  for(int i=0;i<m;i++){
    int a,b,c;cin>>a>>b>>c;
    mat[a/k].a[a%k][b%k]=min(mat[a/k].a[a%k][b%k],c);
  }
  segtree seg(mat);
  while(o--){
    int a,b;cin>>a>>b;
    auto res=seg.prod(a/k,b/k);
    //for(int i=0;i<k;i++)for(int j=0;j<k;j++)cout<<res.a[i][j]<<" \n"[j==k-1];
    int ans=res.a[a%k][b%k];
    if(ans==inf)ans=-1;
    cout<<ans<<endl;
  }
}

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