Submission #1094805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094805		BLOBVISGOD	Toll (BOI17_toll)	C++17	7 / 100	205 ms	107832 KiB

toll

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int oo = 1e9;

struct conn{
    int s;
    vi mc; // from to
    inline int& gt(int x, int y){
        return mc[x*s+y];
    }
    conn operator+(conn b){
        conn ans;
        ans.s = s;
        ans.mc.resize(s*s,oo);
        rep(i,0,s) rep(j,0,s) rep(k,0,s) ans.gt(i,j) = min(ans.gt(i,j), gt(i,k) +b.gt(k,j));
        return ans;
    }
};

template<class T>
struct ST{
    T unite(T l, T r){
        return l+r; // or any associative operation
    }

    int n, mxd;
    vector<vector<T>> suf, pref;

    ST(vector<T> a) : n(sz(a)), mxd(__lg(n)+1), suf(mxd,vector<T>(n)), pref(mxd,vector<T>(n)){
        for (int i=0,w=1; i<mxd; ++i, w*=2)
            for (int b = 0; b < n; b += w){
                int lim = min(b+w,n)-1;
                T cur = a[b];
                for(int k = b; k<lim; cur = unite(cur,a[++k]))
                    pref[i][k] = cur;
                pref[i][lim] = cur;

                cur = a[lim];
                for (int k = lim; k>b; cur = unite(a[--k],cur))
                    suf[i][k] = cur;
                suf[i][b] = cur;
        }
    }

    // halfopen segment [l,r)
    T get(int l, int r){
        if (l==--r) return suf[0][l];
        int d = __lg(l^r);
        return unite(suf[d][l],pref[d][r]);
    }
};


int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int k,n,m,o; cin >> k >> n >> m >> o;
    int N = (n+k-1)/k + 1;
    vector<conn> conns(N);
    rep(i,0,N){
        conns[i].s = k;
        conns[i].mc.resize(k*k,oo);
    }

    while (m--){
        int a,b,t; cin >> a >> b >> t;
        int bl = a/k;
        conns[bl].gt(a%k,b%k) = min(conns[bl].gt(a%k,b%k), t);
    }

    ST st(conns);

    while (o--){
        int a,b; cin >> a >> b;
        int ba = a/k, bb= b/k;
        auto ret = st.get(ba,bb); // halfopen
        int ans = ret.gt(a%k,b%k);
        if (ans==oo) cout << "-1\n";
        else cout << ans << '\n';
    }
}

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