Submission #1285126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285126		kaysan	Toll (BOI17_toll)	C++20	100 / 100	87 ms	21912 KiB

toll

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define pp pop_back
#define pf push_front
#define pt pop_front
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pll pair<ll,ll>
#define pii pair<int,int>
#define vl vector<ll>
#define endl "\n"
#define fr(i,a,b) for(ll i=a; i<=b; i++)
#define fre(i,a,b) for(ll i=a; i>=b; i--)
#define kpnyh ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

const ll INF = (ll)4e18;

ll te,n,m,k,q;
vector<vector<vector<ll>>> st, mtx; // segtree & base matrices

vector<vector<ll>> make_inf_mat(){
    return vector<vector<ll>>( (size_t)k, vector<ll>((size_t)k, INF) );
}

vector<vector<ll>> multiply_mat(const vector<vector<ll>> &A, const vector<vector<ll>> &B){
    vector<vector<ll>> C = make_inf_mat();
    for (ll i=0;i<k;i++){
        for (ll p=0;p<k;p++){
            ll aip = A[i][p];
            if (aip == INF) continue;
            for (ll j=0;j<k;j++){
                ll bpj = B[p][j];
                if (bpj == INF) continue;
                ll cand = aip + bpj;
                if (cand < C[i][j]) C[i][j] = cand;
            }
        }
    }
    return C;
}

// build segtree on [l..r] of base (base size = leafCount)
void build(ll l, ll r, ll idx){
    if (l == r){
        st[idx] = mtx[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(l, mid, idx<<1);
    build(mid+1, r, idx<<1|1);
    st[idx] = multiply_mat(st[idx<<1], st[idx<<1|1]); // left ⊗ right
}

vector<vector<ll>> ans; // accumulated product during query

// ans = ans ⊗ M (in-place)
void ans_mul_with(const vector<vector<ll>> &M){
    vector<vector<ll>> res = make_inf_mat();
    for (ll i=0;i<k;i++){
        for (ll p=0;p<k;p++){
            ll aip = ans[i][p];
            if (aip == INF) continue;
            for (ll j=0;j<k;j++){
                ll b = M[p][j];
                if (b == INF) continue;
                ll cand = aip + b;
                if (cand < res[i][j]) res[i][j] = cand;
            }
        }
    }
    ans.swap(res);
}

// query segtree accumulate into ans; segtree covers [l,r]; query range [x,y]
void qry(ll l, ll r, ll x, ll y, ll idx){
    if (l > y || r < x) return;
    if (l >= x && r <= y){
        ans_mul_with(st[idx]);
        return;
    }
    ll mid = (l + r) >> 1;
    qry(l, mid, x, y, idx<<1);
    qry(mid+1, r, x, y, idx<<1|1);
}

void solve(){
    cin >> k >> n >> m >> q;
    // compute number of layers L and number of transitions (base matrices) leafCount
    ll L = (n + k - 1) / k;
    ll leafCount = max(0LL, L - 1);

    // allocate base matrices for transitions only
    if (leafCount > 0) mtx.assign((size_t)leafCount, make_inf_mat());
    else mtx.clear();

    // read edges: keep only edges from layer u to layer u+1 and within range
    for (ll i=0;i<m;i++){
        ll u,v,w; cin >> u >> v >> w;
        if (u < 0 || v < 0 || u >= n || v >= n) continue;
        ll lu = u / k;
        ll lv = v / k;
        if (lv != lu + 1) continue;           // only adjacent-layer edges
        if (lu < 0 || lu >= leafCount) continue;
        int pu = (int)(u % k);
        int pv = (int)(v % k);
        mtx[(size_t)lu][pu][pv] = min(mtx[(size_t)lu][pu][pv], w);
    }

    int segN = max(1LL, leafCount);
    st.assign(4 * segN, make_inf_mat());
    if (leafCount > 0) build(0, leafCount-1, 1);

    // identity matrix
    vector<vector<ll>> I = make_inf_mat();
    for (int i=0;i<k;i++) I[i][i] = 0;

    while (q--){
        ll a,b; cin >> a >> b;
        if (a < 0 || b < 0 || a >= n || b >= n){
            cout << -1 << endl; continue;
        }
        ll sa = a / k, sb = b / k;
        int pa = (int)(a % k), pb = (int)(b % k);

        if (sa == sb){
            cout << (a==b ? 0 : -1) << endl; continue;
        }
        if (sa > sb){ cout << -1 << endl; continue; }
        if (leafCount == 0){ cout << -1 << endl; continue; }

        ll L_from = sa;
        ll L_to = sb - 1;               // product A_{sa} .. A_{sb-1}
        if (L_from < 0) L_from = 0;
        if (L_to < L_from || L_to >= leafCount){ cout << -1 << endl; continue; }

        // init ans = identity
        ans = I;
        qry(0, leafCount-1, L_from, L_to, 1);
        ll res = ans[pa][pb];
        if (res >= INF/2) cout << -1 << endl;
        else cout << res << endl;
    }
}

int main(){
    kpnyh
    te = 1;
    while (te--) solve();
    return 0;
}

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