oj.uz

Submission #544392

# Submission time Handle Problem Language Result Execution time Memory
544392 2022-04-01T20:32:44 Z huB1erTi2 Toll (BOI17_toll) C++17
10 / 100
 76 ms 15432 KB 
//   _|                                                _|
//   _|  _|    _|    _|    _|_|    _|_|_|      _|_|_|  _|  _|      _|_|      _|_|
//   _|_|      _|    _|  _|_|_|_|  _|    _|  _|_|      _|_|      _|_|_|_|  _|_|_|_|
//   _|  _|    _|    _|  _|        _|    _|      _|_|  _|  _|    _|        _|
//   _|    _|    _|_|_|    _|_|_|  _|_|_|    _|_|_|    _|    _|    _|_|_|    _|_|_|
//                   _|            _|
//               _|_|              _|
#include <iostream>
#include <vector>

using namespace std;

// #define DEBUG
#ifdef DEBUG
#define dassert(x) assert(x);
#define df(...) printf(__VA_ARGS__)
#else
#define dassert(x)
#define df(...)
#endif

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define ir(x, a, b) ((a) <= (x) && (x) <= (b))
#define vec vector
#define sz(x) (ll)x.size()
#define foru(i, n) for (int i = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()

typedef int64_t ll;

int read() {
    int n = 0; bool b = 0; char c = getchar();
    for (; !ir(c, '0', '9'); c = getchar()) b = (c == '-');
    for (; ir(c, '0', '9'); c = getchar()) n = 10*n + (c-'0');
    if (b) return -n;
    return n;
}

int k;
struct mat {
    vec<vec<int>> t = vec<vec<int>>(k, vec<int>(k, 1e9));
    mat operator +(const mat& other) const {
        mat res;
        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < k; ++j) {
                for (int x = 0; x < k; ++x) {
                    res.t[i][j] = min(res.t[i][j], t[i][x] + other.t[x][j]);
                }
            }
        }
        return res;
    }
};

int n, m, o, base;
mat zero;
vec<mat> st;

void init() {
    for (int i = base-1; i > 0; --i) {
        st[i] = st[2*i] + st[2*i+1];
    }
}

mat get(int l, int r) {
    mat lsum = zero, rsum = zero;
    for (l += base, r += base; l < r; l /= 2, r /= 2) {
        if (l & 1) lsum = rsum + st[l++];
        if (r & 1) rsum = st[--r] + rsum;
    }
    return lsum + rsum;
}

int main() {
    df("debug mode\n");
#ifndef DEBUG
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
    cin >> k >> n >> m >> o;
    n /= k;
    
    zero = mat();
    foru (i, k) zero.t[i][i] = 0;
    
    base = 1;
    while (base <= n) base *= 2;
    st.resize(2*base);
    foru (i, m) {
        int a, b, t;
        cin >> a >> b >> t;
        st[base + a/k].t[a%k][b%k] = t;
    }
    init();
    foru (i, o) {
        int a, b;
        cin >> a >> b;
        int res = get(a/k, b/k).t[a%k][b%k];
        if (res == 1e9) cout << "-1\n";
        else cout << res << "\n";
    }
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10080 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 8 ms 584 KB Output is correct
8 Correct 10 ms 592 KB Output is correct
9 Correct 49 ms 12396 KB Output is correct
10 Correct 76 ms 15432 KB Output is correct
11 Correct 57 ms 11712 KB Output is correct
12 Correct 60 ms 14444 KB Output is correct
13 Correct 60 ms 7704 KB Output is correct
14 Correct 40 ms 8132 KB Output is correct
15 Correct 40 ms 6448 KB Output is correct
16 Correct 41 ms 6476 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -