Submission #1094842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094842		BLOBVISGOD	Toll (BOI17_toll)	C++17	0 / 100	37 ms	25680 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;
    }
};

struct segtree{
    int k, n;
    conn id;
    vector<conn> a;
    segtree(vector<conn> b, int k) : k(k) {
        id.s = k;
        id.mc.resize(k*k,oo);
        rep(i,0,k) id.gt(i,i) = 0;
        n = 1;
        while(n<sz(b)) n*=2;
        a.resize(n*2,{k});
        rep(i,0,sz(b)) a[i+n] = b[i];
        for(int i = n-1; i>0; --i) a[i] = a[i*2] + a[i*2+1];
    }
    conn gt(int i, int l, int r, int ql, int qr){
        if (l>=qr or r<=ql) return id;
        if (l>=ql and r<=qr) return a[i];
        int mid = (l+r)/2;
        return gt(i*2,l,mid,ql,qr) + gt(i*2+1,mid,r,ql,qr);
    }
    conn get(int l, int r) {return gt(1,0,n,l,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);
    }

    segtree st(conns, k);
    
    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: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44