oj.uz

Submission #1094805

# Submission time Handle Problem Language Result Execution time Memory
1094805 2024-09-30T15:36:02 Z BLOBVISGOD Toll (BOI17_toll) C++17
7 / 100
 205 ms 107832 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 107832 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1824 KB Output is correct
6 Correct 5 ms 1624 KB Output is correct
7 Correct 5 ms 1628 KB Output is correct
8 Correct 195 ms 107788 KB Output is correct
9 Correct 199 ms 107608 KB Output is correct
10 Correct 191 ms 106804 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 52032 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 107832 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1824 KB Output is correct
6 Correct 5 ms 1624 KB Output is correct
7 Correct 5 ms 1628 KB Output is correct
8 Correct 195 ms 107788 KB Output is correct
9 Correct 199 ms 107608 KB Output is correct
10 Correct 191 ms 106804 KB Output is correct
11 Correct 124 ms 52032 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Runtime error 1 ms 604 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -