Submission #1115963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115963		vjudge1	Toll (BOI17_toll)	C++17	100 / 100	331 ms	70484 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
class T{
    public:
    vector<vector<int>> mat;
    T(): mat(5,vector<int>(5,1e18)){};
};
class U{
    public:
    int temp;
    U(): temp(-1){};
};
vector<vector<int>> multiply(vector<vector<int>> &a,vector<vector<int>> &b){
    vector<vector<int>> curr(a.size(),vector<int>(5,1e18));
    for(int i=0;i<a.size();i++){
        for(int k=0;k<5;k++){
            for(int j=0;j<5;j++){
                curr[i][j]=min(curr[i][j],a[i][k]+b[k][j]);
            }
        }
    }
    return curr;
}
class trtr{
    public:
    T operator()(T trl,T trr){
        T pa;
        if(trl.mat[0][0]==-1){
            return trr;
        }
        if(trr.mat[0][0]==-1){
            return trl;
        }
        pa.mat=multiply(trl.mat,trr.mat);
        return pa;
    }
};
class lztr{
    public:
    T operator()(U &app,T tr){
        return tr;
    }
};
class lzlz{
    public:
    U operator()(U &app,U lz){
        return lz;
    }
};
void print(T &check){
    cout << "GOT" << endl;
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            cout << check.mat[i][j] << ' ';
        }
        cout << endl;
    }
}
template<class T,class U,class trtr,class lztr,class lzlz> struct segtree{
    vector<T> seg;
    vector<U> d;
    trtr TT;
    lztr UT;
    lzlz UU;
    T Tid;
    U Uid;
    int n;
    int lg;
    segtree(T Tid,U Uid,trtr TT,lztr UT,lzlz UU): Tid(Tid),Uid(Uid),TT(TT),UT(UT),UU(UU){};
    void refresh(int v){
        seg[v]=TT(seg[v<<1],seg[(v<<1)|1]);
    }
    void build(vector<T> &a){
        int siz=a.size();
        n=1;
        while(n<siz){
            n<<=1;
        }
        lg=__lg(n);
        seg.assign(n<<1,Tid);
        d.assign(n,Uid);
        copy(a.begin(),a.end(),seg.begin()+n);
        for(int i=n-1;i>1;i--){
            refresh(i);
        }
    }
    void apply(int v,U f){
        seg[v]=UT(f,seg[v]);
        if(v<n){
            d[v]=UU(f,d[v]);
        }
    }
    void push(int v){
        apply(v<<1,d[v]);
        apply((v<<1)|1,d[v]);
        d[v]=Uid;
    }
    void update(int l,int r,U f){
        if(l==r){
            return;
        }
        l+=n,r+=n;
        int l0=l,r0=r;
        for(int i=lg;i>=1;i--){
            if((l>>i<<i)!=l){
                push(l>>i);
            }
            if((r>>i<<i)!=r){
                push(r>>i);
            }
        }
        for(;l<r;l>>=1,r>>=1){
            if(l&1){
                apply(l,f);
                l++;
            }
            if(r&1){
                r--;
                apply(r,f);
            }
        }
        l=l0,r=r0;
        for(int i=1;i<=lg;i++){
            if((l>>i<<i)!=l){
                refresh(l>>i);
            }
            if((r>>i<<i)!=r){
                refresh(r>>i);
            }
        }
    }
    T query(int l,int r){
        if(l==r){
            return Tid;
        }
        l+=n,r+=n;
        for(int i=lg;i>=1;i--){
            if((l>>i<<i)!=l){
                push(l>>i);
            }
            if((r>>i<<i)!=r){
                push(r>>i);
            }
        }
        T trl=Tid,trr=Tid;
        for(;l<r;l>>=1,r>>=1){
            if(l&1){
                trl=TT(trl,seg[l]);
                l++;
            }
            if(r&1){
                r--;
                trr=TT(seg[r],trr);
            }
        }
        return TT(trl,trr);
    }
};
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    trtr TT;
    lztr UT;
    lzlz UU;
    T Tid;
    U Uid;
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            Tid.mat[i][j]=-1;
        }
    }
    segtree<T,U,trtr,lztr,lzlz> seg(Tid,Uid,TT,UT,UU);
    int k,n,m,o;
    cin >> k >> n >> m >> o;
    vector<T> a((n-1)/k+1);
    for(int i=0;i<m;i++){
        int u,v,t;
        cin >> u >> v >> t;
        a[u/k].mat[u%k][v%k]=t;
    }
    /*for(int i=0;i<a.size();i++){
        cout << i << ": " << endl;
        print(a[i]);
    }*/
    seg.build(a);
    while(o--){
        int u,v;
        cin >> u >> v;
        if(u/k==v/k){
            cout << -1 << endl;
            continue;
        }
        vector<vector<int>> base(1,vector<int>(5,1e18));
        base[0][u%k]=0;
        T trans=seg.query(u/k,v/k);
        base=multiply(base,trans.mat);
        if(base[0][v%k]==1e18){
            base[0][v%k]=-1;
        }
        cout << base[0][v%k] << endl;
    }
}

Compilation message (stderr)

toll.cpp: In function 'std::vector<std::vector<long long int> > multiply(std::vector<std::vector<long long int> >&, std::vector<std::vector<long long int> >&)':
toll.cpp:17:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~
toll.cpp: In instantiation of 'segtree<T, U, trtr, lztr, lzlz>::segtree(T, U, trtr, lztr, lzlz) [with T = T; U = U; trtr = trtr; lztr = lztr; lzlz = lzlz]':
toll.cpp:174:53:   required from here
toll.cpp:68:7: warning: 'segtree<T, U, trtr, lztr, lzlz>::Uid' will be initialized after [-Wreorder]
   68 |     U Uid;
      |       ^~~
toll.cpp:64:10: warning:   'trtr segtree<T, U, trtr, lztr, lzlz>::TT' [-Wreorder]
   64 |     trtr TT;
      |          ^~
toll.cpp:71:5: warning:   when initialized here [-Wreorder]
   71 |     segtree(T Tid,U Uid,trtr TT,lztr UT,lzlz UU): Tid(Tid),Uid(Uid),TT(TT),UT(UT),UU(UU){};
      |     ^~~~~~~

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