Submission #269904

#	Time	Username	Problem	Language	Result	Execution time	Memory
269904		brcode	Toll (BOI17_toll)	C++14	100 / 100	857 ms	32760 KiB

toll

#include <iostream>

using namespace std;
const int MAXN = 5e4+5;
struct node{
    int weight[6][6];
    bool realnode = false;
    void init(){
        for(int i=0;i<=5;i++){
            for(int j=0;j<=5;j++){
                weight[i][j] = 1e9;
            }
        }
        
    }
    void init2(){
        for(int i=0;i<=5;i++){
            for(int j=0;j<=5;j++){
                weight[i][j] = 0;
            }
        }
        
    }
    void upd(int x,int y,int w){
        //cout<<x<<" "<<y<<" "<<weight[x][y]<<endl;
        weight[x][y] = min(weight[x][y],w);
        
    }
};
node seg[4*MAXN];
 int k,n,m,o;
void build(int curr,int l,int r){
    if(l==r){
        seg[curr].init();
        seg[curr].realnode = true;
        return;
    }
    int mid = (l+r)/2;
    build(2*curr,l,mid);
    build(2*curr+1,mid+1,r);
    seg[curr].init();
    seg[curr].realnode = true;
}
void update(int curr,int l,int r,int pos,int from,int to,int val){
    
    if(l==r){
        
        seg[curr].upd(from,to,val);
      
        return;
    }
    int mid = (l+r)/2;
    if(pos<=mid){
        update(2*curr,l,mid,pos,from,to,val);
    }else{
        update(2*curr+1,mid+1,r,pos,from,to,val);
    }
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            for(int newmid=0;newmid<5;newmid++){
                seg[curr].weight[i][j] = min(seg[curr].weight[i][j],seg[2*curr].weight[i][newmid]+seg[2*curr+1].weight[newmid][j]);
                
            }
        }
    }
    
}
node query(int curr,int l,int r,int tl,int tr){
    if(r<tl||l>tr){
        node tmp;
        
        tmp.init();
        return tmp;
    }
    if(tl<=l && r<=tr){
       // cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<endl;
       // cout<<seg[curr].weight[0][0]<<endl;
        return seg[curr];
    }
    int mid = (l+r)/2;
    node templ = query(2*curr,l,mid,tl,tr);
    node tempr = query(2*curr+1,mid+1,r,tl,tr);
    
    node resnode;
    resnode.realnode = true;
    resnode.init();
    if(templ.realnode == false){
        return tempr;
    }
    if(tempr.realnode == false){
        return templ;
    }
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            for(int newmid=0;newmid<5;newmid++){
                
                    resnode.weight[i][j] = min(resnode.weight[i][j],templ.weight[i][newmid]+tempr.weight[newmid][j]);
               
                
            }
        }
    }
   // cout<<l<<" "<<mid<<endl;
   // cout<<mid+1<<" "<<r<<endl;
    //cout<<tempr.weight[0][0]<<endl;
    return resnode;
}
int main(){
   
    cin>>k>>n>>m>>o;
    build(1,0,(n-1)/k);
    for(int i=1;i<=m;i++){
        int x,y,w;
        cin>>x>>y>>w;
        update(1,0,(n-1)/k,x/k,x%k,y%k,w);
    }
    while(o--){
        int x,y;
        cin>>x>>y;
        if(y/k<=x/k){
            cout<<-1<<endl;
            continue;
        }
        //cout<<x%k<<" "<<y%k<<endl;
        int res = query(1,0,(n-1)/k,x/k,(y/k)-1).weight[x%k][y%k];
        //cout<<x/k<<" "<<(y/k)-1<<endl;
        if(res == 1e9){
            cout<<-1<<endl;
            continue;
        }
        cout<<res<<endl;
    }
    
}

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