oj.uz

답안 #544392

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 50 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 50 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -