oj.uz

답안 #1115795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1115795 2024-11-21T01:14:20 Z vjudge1 Toll (BOI17_toll) C++17
100 / 100
 240 ms 75084 KB 
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

const int inf = 1e9;

template<class T>
struct matrix{
    int n, m;
    vector<vector<T>> data;
    vector<T> &operator[](int i){
        assert(0 <= i && i < n);
        return data[i];
    }
    const vector<T> &operator[](int i) const{
        assert(0 <= i && i < n);
        return data[i];
    }
    matrix &inplace_slice(int il, int ir, int jl, int jr){
        assert(0 <= il && il <= ir && ir <= n);
        assert(0 <= jl && jl <= jr && jr <= m);
        n = ir - il, m = jr - jl;
        if(il > 0) for(auto i = 0; i < n; ++ i) swap(data[i], data[il + i]);
        data.resize(n);
        for(auto &row: data){
            row.erase(row.begin(), row.begin() + jl);
            row.resize(m);
        }
        return *this;
    }
    matrix slice(int il, int ir, int jl, int jr) const{
        return matrix(*this).inplace_slice(il, ir, jl, jr);
    }
    matrix &inplace_row_slice(int il, int ir){
        assert(0 <= il && il <= ir && ir <= n);
        n = ir - il;
        if(il > 0) for(auto i = 0; i < n; ++ i) swap(data[i], data[il + i]);
        data.resize(n);
        return *this;
    }
    matrix row_slice(int il, int ir) const{
        return matrix(*this).inplace_row_slice(il, ir);
    }
    matrix &inplace_column_slice(int jl, int jr){
        assert(0 <= jl && jl <= jr && jr <= m);
        m = jr - jl;
        for(auto &row: data){
            row.erase(row.begin(), row.begin() + jl);
            row.resize(m);
        }
        return *this;
    }
    matrix column_slice(int jl, int jr) const{
        return matrix(*this).inplace_column_slice(jl, jr);
    }
    bool operator==(const matrix &a) const{
        assert(n == a.n && m == a.m);
        return data == a.data;
    }
    bool operator!=(const matrix &a) const{
        assert(n == a.n && m == a.m);
        return data != a.data;
    }
    matrix &operator+=(const matrix &a){
        assert(n == a.n && m == a.m);
        for(auto i = 0; i < n; ++ i) for(auto j = 0; j < m; ++ j) data[i][j] += a[i][j];
        return *this;
    }
    matrix operator+(const matrix &a) const{
        return matrix(*this) += a;
    }
    matrix &operator-=(const matrix &a){
        assert(n == a.n && m == a.m);
        for(auto i = 0; i < n; ++ i) for(auto j = 0; j < m; ++ j) data[i][j] -= a[i][j];
        return *this;
    }
    matrix operator-(const matrix &a) const{
        return matrix(*this) -= a;
    }
    matrix operator*=(const matrix &a){
        assert(m == a.n);
        int l = a.m;
        matrix res(n, l, inf, inf);
        for(auto i = 0; i < n; ++ i) for(auto j = 0; j < m; ++ j) for(auto k = 0; k < l; ++ k) res[i][k] = min(res[i][k], data[i][j] + a[j][k]);
        return *this = res;
    }
    matrix operator*(const matrix &a) const{
        return matrix(*this) *= a;
    }
    matrix &operator*=(T c){
        for(auto i = 0; i < n; ++ i) for(auto j = 0; j < m; ++ j) data[i][j] *= c;
        return *this;
    }
    matrix operator*(T c) const{
        return matrix(*this) *= c;
    }
    template<class U, typename enable_if<is_integral<U>::value>::type* = nullptr>
    matrix &inplace_power(U e){
        assert(n == m && e >= 0);
        matrix res(n, n, T{1});
        for(; e; *this *= *this, e >>= 1) if(e & 1) res *= *this;
        return *this = res;
    }
    template<class U>
    matrix power(U e) const{
        return matrix(*this).inplace_power(e);
    }
    matrix &inplace_transpose(){
        assert(n == m);
        for(auto i = 0; i < n; ++ i) for(auto j = i + 1; j < n; ++ j) swap(data[i][j], data[j][i]);
        return *this;
    }
    matrix transpose() const{
        if(n == m) return matrix(*this).inplace_transpose();
        matrix res(m, n);
        for(auto i = 0; i < n; ++ i) for(auto j = 0; j < m; ++ j) res[j][i] = data[i][j];
        return res;
    }
    vector<T> operator*(const vector<T> &v) const{
        assert(m == (int)v.size());
        vector<T> res(n, T{0});
        for(auto i = 0; i < n; ++ i) for(auto j = 0; j < m; ++ j) res[i] += data[i][j] * v[j];
        return res;
    }
    // Assumes T is either a floating, integral, or a modular type.
    // If T is a floating type, O(up_to) divisions with O(n * m * up_to) additions, subtractions, and multiplications.
    // Otherwise, O(n * up_to * log(size)) divisions with O(n * m * up_to) additions, subtractions, and multiplications.
    // Returns {REF matrix, determinant, rank}
    tuple<matrix &, T, int> inplace_REF(int up_to = -1){
        if(n == 0) return {*this, T{1}, 0};
        if(!~up_to) up_to = m;
        T det = 1;
        int rank = 0;
        for(auto j = 0; j < up_to; ++ j){
            if constexpr(is_floating_point_v<T>){
                static const T eps = 1e-9;
                int pivot = rank;
                for(auto i = rank + 1; i < n; ++ i) if(abs(data[pivot][j]) < abs(data[i][j])) pivot = i;
                if(rank != pivot){
                    swap(data[rank], data[pivot]);
                    det *= -1;
                }
                if(abs(data[rank][j]) <= eps) continue;
                det *= data[rank][j];
                T inv = 1 / data[rank][j];
                for(auto i = rank + 1; i < n; ++ i) if(abs(data[i][j]) > eps){
                    T coef = data[i][j] * inv;
                    for(auto k = j; k < m; ++ k) data[i][k] -= coef * data[rank][k];
                }
                ++ rank;
            }
            else{
                for(auto i = rank + 1; i < n; ++ i) while(data[i][j]){
                    T q;
                    if constexpr(is_integral_v<T> || is_same_v<T, __int128_t> || is_same_v<T, __uint128_t>) q = data[rank][j] / data[i][j];
                    else q = data[rank][j].data / data[i][j].data;
                    if(q) for(auto k = j; k < m; ++ k) data[rank][k] -= q * data[i][k];
                    swap(data[rank], data[i]);
                    det *= -1;
                }
                if(rank == j) det *= data[rank][j];
                else det = T{0};
                if(data[rank][j]) ++ rank;
            }
            if(rank == n) break;
        }
        return {*this, det, rank};
    }
    // Assumes T is either a floating, integral, or a modular type.
    // If T is a floating type, O(up_to) divisions with O(n * m * up_to) additions, subtractions, and multiplications.
    // Otherwise, O(n * up_to * log(size)) divisions with O(n * m * up_to) additions, subtractions, and multiplications.
    // Returns {REF matrix, determinant, rank}
    tuple<matrix, T, int> REF(int up_to = -1) const{
        return matrix(*this).inplace_REF(up_to);
    }
    // Assumes T is a field.
    // O(up_to) divisions with O(n * m * up_to) additions, subtractions, and multiplications.
    // Returns {REF matrix, determinant, rank}
    tuple<matrix &, T, int> inplace_REF_field(int up_to = -1){
        if(n == 0) return {*this, T{1}, 0};
        if(!~up_to) up_to = m;
        T det = T{1};
        int rank = 0;
        for(auto j = 0; j < up_to; ++ j){
            int pivot = -1;
            for(auto i = rank; i < n; ++ i) if(data[i][j] != T{0}){
                pivot = i;
                break;
            }
            if(!~pivot){
                det = T{0};
                continue;
            }
            if(rank != pivot){
                swap(data[rank], data[pivot]);
                det *= -1;
            }
            det *= data[rank][j];
            T inv = 1 / data[rank][j];
            for(auto i = rank + 1; i < n; ++ i) if(data[i][j] != T{0}){
                T coef = data[i][j] * inv;
                for(auto k = j; k < m; ++ k) data[i][k] -= coef * data[rank][k];
            }
            ++ rank;
            if(rank == n) break;
        }
        return {*this, det, rank};
    }
    // Assumes T is a field.
    // O(up_to) divisions with O(n * m * up_to) additions, subtractions, and multiplications.
    // Returns {REF matrix, determinant, rank}
    tuple<matrix, T, int> REF_field(int up_to = -1) const{
        return matrix(*this).inplace_REF_field(up_to);
    }
    // Assumes T is a field.
    // O(n) divisions with O(n^3) additions, subtractions, and multiplications.
    optional<matrix> inverse() const{
        assert(n == m);
        if(n == 0) return *this;
        auto a = data;
        auto res = multiplicative_identity();
        for(auto j = 0; j < n; ++ j){
            int rank = j, pivot = -1;
            if constexpr(is_floating_point_v<T>){
                static const T eps = 1e-9;
                pivot = rank;
                for(auto i = rank + 1; i < n; ++ i) if(abs(a[pivot][j]) < abs(a[i][j])) pivot = i;
                if(abs(a[pivot][j]) <= eps) return {};
            }
            else{
                for(auto i = rank; i < n; ++ i) if(a[i][j] != T{0}){
                    pivot = i;
                    break;
                }
                if(!~pivot) return {};
            }
            swap(a[rank], a[pivot]), swap(res[rank], res[pivot]);
            T inv = 1 / a[rank][j];
            for(auto k = 0; k < n; ++ k) a[rank][k] *= inv, res[rank][k] *= inv;
            for(auto i = 0; i < n; ++ i){
                if constexpr(is_floating_point_v<T>){
                    static const T eps = 1e-9;
                    if(i != rank && abs(a[i][j]) > eps){
                        T d = a[i][j];
                        for(auto k = 0; k < n; ++ k) a[i][k] -= d * a[rank][k], res[i][k] -= d * res[rank][k];
                    }
                }
                else if(i != rank && a[i][j] != T{0}){
                    T d = a[i][j];
                    for(auto k = 0; k < n; ++ k) a[i][k] -= d * a[rank][k], res[i][k] -= d * res[rank][k];
                }
            }
        }
        return res;
    }
    // Assumes T is either a floating, integral, or a modular type.
    // If T is a floating type, O(n) divisions with O(n^3) additions, subtractions, and multiplications.
    // Otherwise, O(n^2 * log(size)) divisions with O(n^3) additions, subtractions, and multiplications.
    T determinant() const{
        assert(n == m);
        return get<1>(REF());
    }
    // Assumes T is a field.
    // O(n) divisions with O(n^3) additions, subtractions, and multiplications.
    T determinant_field() const{
        assert(n == m);
        return get<1>(REF_field());
    }
    // Assumes T is either a floating, integral, or a modular type.
    // If T is a floating type, O(n) divisions with O(n^3) additions, subtractions, and multiplications.
    // Otherwise, O(n^2 * log(size)) divisions with O(n^3) additions, subtractions, and multiplications.
    int rank() const{
        return get<2>(REF());
    }
    // Assumes T is a field.
    // O(n) divisions with O(n^3) additions, subtractions, and multiplications.
    int rank_field() const{
        return get<2>(REF_field());
    }
    // Regarding the matrix as a system of linear equations by separating first m-1 columns, find a solution of the linear equation.
    // Assumes T is a field
    // O(n * m^2)
    optional<vector<T>> find_a_solution() const{
        assert(m >= 1);
        auto [ref, _, rank] = REF_field(m - 1);
        for(auto i = rank; i < n; ++ i) if(ref[i][m - 1] != T{0}) return {};
        vector<T> res(m - 1);
        for(auto i = rank - 1; i >= 0; -- i){
            int pivot = 0;
            while(pivot < m - 1 && ref[i][pivot] == T{0}) ++ pivot;
            assert(pivot < m - 1);
            res[pivot] = ref[i][m - 1];
            for(auto j = pivot + 1; j < m - 1; ++ j) res[pivot] -= ref[i][j] * res[j];
            res[pivot] /= ref[i][pivot];
        }
        return res;
    }
    // O(n * 2^n)
    T permanent() const{
        assert(n <= 30 && n == m);
        T perm = n ? 0 : 1;
        vector<T> sum(n);
        for(auto order = 1; order < 1 << n; ++ order){
            int j = __lg(order ^ order >> 1 ^ order - 1 ^ order - 1 >> 1), sign = (order ^ order >> 1) & 1 << j ? 1 : -1;
            T prod = order & 1 ? -1 : 1;
            if((order ^ order >> 1) & 1 << j) for(auto i = 0; i < n; ++ i) prod *= sum[i] += data[i][j];
            else for(auto i = 0; i < n; ++ i) prod *= sum[i] -= data[i][j];
            perm += prod;
        }
        return perm * (n & 1 ? -1 : 1);
    }
    template<class output_stream>
    friend output_stream &operator<<(output_stream &out, const matrix &a){
        out << "\n";
        for(auto i = 0; i < a.n; ++ i){
            for(auto j = 0; j < a.m; ++ j) out << a[i][j] << " ";
            out << "\n";
        }
        return out;
    }
    matrix(int n, int m, T init_diagonal = T{0}, T init_off_diagonal = T{0}): n(n), m(m){
        assert(n >= 0 && m >= 0);
        data.assign(n, vector<T>(m, T{0}));
        for(auto i = 0; i < n; ++ i) for(auto j = 0; j < m; ++ j) data[i][j] = i == j ? init_diagonal : init_off_diagonal;
    }
    matrix(int n, int m, const vector<vector<T>> &a): n(n), m(m), data(a){ }
    static matrix additive_identity(int n, int m){
        return matrix(n, m, T{0}, T{0});
    }
    static matrix multiplicative_identity(int n, int m){
        return matrix(n, m, T{1}, T{0});
    }
};
template<class T>
matrix<T> operator*(T c, matrix<T> a){
    for(auto i = 0; i < a.n; ++ i) for(auto j = 0; j < a.m; ++ j) a[i][j] = c * a[i][j];
    return a;
}
// Multiply a row vector v on the left
template<class T>
vector<T> operator*(const vector<T> &v, const matrix<T> &a){
    assert(a.n == (int)size(v));
    vector<T> res(a.m, T{0});
    for(auto i = 0; i < a.n; ++ i) for(auto j = 0; j < a.m; ++ j) res[j] += v[i] * a[i][j];
    return res;
}

void solve() {
    int K, n, m, q;
    cin >> K >> n >> m >> q;

    int layer = (n - 1) / K;
    vector<matrix<int>> vec(layer, matrix(K, K, inf, inf));
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        vec[u / K][u % K][v % K] = min(vec[u / K][u % K][v % K], w);
    }

    // for (int i = 0; i < layer; ++i) {
    //     cout << vec[i] << endl;
    // }

    vector<vector<matrix<int>>> jmp({vec});
    for (int i = 1, p = 1; p << 1 <= layer; ++i, p <<= 1) {
        jmp.emplace_back(isz(jmp[i - 1]) - p, matrix(K, K, inf, inf));
        for (int j = 0; j + p < isz(jmp[i - 1]); ++j) {
            jmp[i][j] = jmp[i - 1][j] * jmp[i - 1][j + p];
            // cout << jmp[i][j] << endl;
        }
    }

    auto query = [&](int l, int r, int st, int en) -> int {
        int len = r - l, cnt = 0;
        matrix res(K, K, inf, inf);
        for (int i = 0; i < K; ++i) {
            res[i][i] = 0;
        }
        while (len) {
            if (len & 1) {
                res *= jmp[cnt][l];
                l += 1 << cnt;
            }
            len >>= 1, ++cnt;
        }
        return (res[st][en] == inf ? -1 : res[st][en]);
    };

    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << query(u / K, v / K, u % K, v % K) << endl;
    }
}

signed main() {

#ifndef CDuongg
    if (fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 240 ms 75052 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 5 ms 1360 KB Output is correct
6 Correct 5 ms 1360 KB Output is correct
7 Correct 5 ms 1360 KB Output is correct
8 Correct 220 ms 75084 KB Output is correct
9 Correct 222 ms 74904 KB Output is correct
10 Correct 207 ms 74232 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 59448 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 24 ms 1360 KB Output is correct
8 Correct 25 ms 1104 KB Output is correct
9 Correct 210 ms 74796 KB Output is correct
10 Correct 186 ms 50360 KB Output is correct
11 Correct 174 ms 59504 KB Output is correct
12 Correct 177 ms 49360 KB Output is correct
13 Correct 117 ms 26508 KB Output is correct
14 Correct 104 ms 28940 KB Output is correct
15 Correct 103 ms 25388 KB Output is correct
16 Correct 96 ms 25228 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Correct 3 ms 1324 KB Output is correct
7 Correct 3 ms 1104 KB Output is correct
8 Correct 3 ms 848 KB Output is correct
9 Correct 3 ms 848 KB Output is correct
10 Correct 196 ms 74732 KB Output is correct
11 Correct 153 ms 59448 KB Output is correct
12 Correct 156 ms 49980 KB Output is correct
13 Correct 163 ms 50420 KB Output is correct
14 Correct 150 ms 49724 KB Output is correct
15 Correct 87 ms 25228 KB Output is correct
16 Correct 81 ms 25236 KB Output is correct

Subtask #4
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Correct 3 ms 1324 KB Output is correct
7 Correct 3 ms 1104 KB Output is correct
8 Correct 3 ms 848 KB Output is correct
9 Correct 3 ms 848 KB Output is correct
10 Correct 196 ms 74732 KB Output is correct
11 Correct 153 ms 59448 KB Output is correct
12 Correct 156 ms 49980 KB Output is correct
13 Correct 163 ms 50420 KB Output is correct
14 Correct 150 ms 49724 KB Output is correct
15 Correct 87 ms 25228 KB Output is correct
16 Correct 81 ms 25236 KB Output is correct
17 Correct 168 ms 59380 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 10 ms 1360 KB Output is correct
24 Correct 10 ms 1272 KB Output is correct
25 Correct 14 ms 848 KB Output is correct
26 Correct 12 ms 1076 KB Output is correct
27 Correct 224 ms 74796 KB Output is correct
28 Correct 178 ms 50236 KB Output is correct
29 Correct 173 ms 50276 KB Output is correct
30 Correct 168 ms 49724 KB Output is correct

Subtask #5
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 240 ms 75052 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 5 ms 1360 KB Output is correct
6 Correct 5 ms 1360 KB Output is correct
7 Correct 5 ms 1360 KB Output is correct
8 Correct 220 ms 75084 KB Output is correct
9 Correct 222 ms 74904 KB Output is correct
10 Correct 207 ms 74232 KB Output is correct
11 Correct 166 ms 59448 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 24 ms 1360 KB Output is correct
18 Correct 25 ms 1104 KB Output is correct
19 Correct 210 ms 74796 KB Output is correct
20 Correct 186 ms 50360 KB Output is correct
21 Correct 174 ms 59504 KB Output is correct
22 Correct 177 ms 49360 KB Output is correct
23 Correct 117 ms 26508 KB Output is correct
24 Correct 104 ms 28940 KB Output is correct
25 Correct 103 ms 25388 KB Output is correct
26 Correct 96 ms 25228 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 592 KB Output is correct
31 Correct 1 ms 504 KB Output is correct
32 Correct 3 ms 1324 KB Output is correct
33 Correct 3 ms 1104 KB Output is correct
34 Correct 3 ms 848 KB Output is correct
35 Correct 3 ms 848 KB Output is correct
36 Correct 196 ms 74732 KB Output is correct
37 Correct 153 ms 59448 KB Output is correct
38 Correct 156 ms 49980 KB Output is correct
39 Correct 163 ms 50420 KB Output is correct
40 Correct 150 ms 49724 KB Output is correct
41 Correct 87 ms 25228 KB Output is correct
42 Correct 81 ms 25236 KB Output is correct
43 Correct 168 ms 59380 KB Output is correct
44 Correct 1 ms 336 KB Output is correct
45 Correct 1 ms 336 KB Output is correct
46 Correct 1 ms 336 KB Output is correct
47 Correct 1 ms 336 KB Output is correct
48 Correct 1 ms 336 KB Output is correct
49 Correct 10 ms 1360 KB Output is correct
50 Correct 10 ms 1272 KB Output is correct
51 Correct 14 ms 848 KB Output is correct
52 Correct 12 ms 1076 KB Output is correct
53 Correct 224 ms 74796 KB Output is correct
54 Correct 178 ms 50236 KB Output is correct
55 Correct 173 ms 50276 KB Output is correct
56 Correct 168 ms 49724 KB Output is correct
57 Correct 232 ms 49204 KB Output is correct
58 Correct 239 ms 75052 KB Output is correct
59 Correct 188 ms 59704 KB Output is correct