結果

問題 No.2640 traO Stamps
ユーザー zawakasuzawakasu
提出日時 2024-02-19 22:09:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 69 ms / 2,000 ms
コード長 6,281 bytes
コンパイル時間 2,117 ms
コンパイル使用メモリ 211,328 KB
実行使用メモリ 7,552 KB
最終ジャッジ日時 2024-02-19 22:09:28
合計ジャッジ時間 6,629 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge16
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 1 ms
6,676 KB
testcase_04 AC 2 ms
6,676 KB
testcase_05 AC 2 ms
6,676 KB
testcase_06 AC 53 ms
6,676 KB
testcase_07 AC 56 ms
6,676 KB
testcase_08 AC 63 ms
7,040 KB
testcase_09 AC 50 ms
6,676 KB
testcase_10 AC 61 ms
7,040 KB
testcase_11 AC 50 ms
6,676 KB
testcase_12 AC 58 ms
7,296 KB
testcase_13 AC 50 ms
6,676 KB
testcase_14 AC 62 ms
7,168 KB
testcase_15 AC 51 ms
6,676 KB
testcase_16 AC 52 ms
6,912 KB
testcase_17 AC 57 ms
7,040 KB
testcase_18 AC 54 ms
6,676 KB
testcase_19 AC 62 ms
7,296 KB
testcase_20 AC 60 ms
7,296 KB
testcase_21 AC 51 ms
6,676 KB
testcase_22 AC 62 ms
7,296 KB
testcase_23 AC 51 ms
6,676 KB
testcase_24 AC 54 ms
6,676 KB
testcase_25 AC 62 ms
7,552 KB
testcase_26 AC 52 ms
7,552 KB
testcase_27 AC 54 ms
7,552 KB
testcase_28 AC 53 ms
7,552 KB
testcase_29 AC 58 ms
7,552 KB
testcase_30 AC 69 ms
7,424 KB
testcase_31 AC 68 ms
7,424 KB
testcase_32 AC 63 ms
6,784 KB
testcase_33 AC 64 ms
6,912 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>




namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa


namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa


#include <type_traits>

namespace zawa {

template <class Group>
class FenwickTree {
private:
    using Value = typename Group::Element;

    usize n_;
    u32 bitWidth_;
    std::vector<Value> a_, dat_;

    constexpr i32 lsb(i32 x) const noexcept {
        return x & -x;
    }
    
    // a[i] <- a[i] + v
    void addDat(i32 i, const Value& v) {
        assert(0 <= i and i < static_cast<i32>(n_));
        for ( i++ ; i < static_cast<i32>(dat_.size()) ; i += lsb(i)) {
            dat_[i] = Group::operation(dat_[i], v);
        }
    }

    // return a[0] + a[1] + .. + a[i - 1]
    Value product(i32 i) const {
        assert(0 <= i and i <= static_cast<i32>(n_));
        Value res{ Group::identity() };
        for ( ; i > 0 ; i -= lsb(i)) {
            res = Group::operation(res, dat_[i]);
        }
        return res;
    }

public:
    FenwickTree() : n_{}, bitWidth_{}, a_{}, dat_{} {}

    FenwickTree(usize n) : n_{ n }, bitWidth_{ std::__lg(static_cast<u32>(n)) + 1 }, a_(n), dat_(n + 1, Group::identity()) {
        dat_.shrink_to_fit();
    }

    FenwickTree(const std::vector<Value>& a) : n_{ a.size() }, bitWidth_{ std::__lg(static_cast<u32>(a.size())) + 1 }, a_(a), dat_(a.size() + 1, Group::identity()) {
        dat_.shrink_to_fit();  
        for (i32 i{} ; i < static_cast<i32>(n_) ; i++) {
            addDat(i, a[i]);
        }
    }

    // return a[i]
    const Value& get(usize i) const noexcept {
        assert(i < n_);
        return a_[i];
    }

    // return a[i]
    const Value& operator[](usize i) const noexcept {
        assert(i < n_);
        return a_[i];
    }

    usize size() const noexcept {
        return n_;
    }

    // a[i] <- a[i] + v
    void operation(usize i, const Value& v) {
        assert(i < n_);
        addDat(i, v);
        a_[i] = Group::operation(a_[i], v);
    }

    // a[i] <- v
    void set(usize i, const Value& v) {
        assert(i < n_);
        addDat(i, Group::operation(Group::inverse(a_[i]), v));
        a_[i] = v;
    }

    // return a[0] + a[1] + ... + a[r - 1]
    Value prefixProduct(usize r) const {
        assert(r <= n_);
        return product(r);
    }

    // return a[l] + a[l + 1] ... + a[r - 1]
    Value product(usize l, usize r) const {
        assert(l <= r and r <= n_);
        return Group::operation(Group::inverse(product(l)), product(r));
    }

    template <class Function>
    u32 maxRight(usize l, const Function& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(Value)>>, "maxRight's argument f must be function bool(T)");
        assert(l < n_);
        Value sum{ Group::inverse(product(l)) }; 
        u32 r{};
        for (u32 bit{ bitWidth_ } ; bit ; ) {
            bit--;
            u32 nxt{ r | (1u << bit) };
            if (nxt < dat_.size() and f(Group::operation(sum, dat_[nxt]))) {
                sum = Group::operation(sum, dat_[nxt]);
                r = std::move(nxt);
            }
        }
        assert(l <= r);
        return r;
    }

    template <class Function>
    u32 minLeft(usize r, const Function& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(Value)>>, "minLeft's argument f must be function bool(T)");
        assert(r <= n_);
        Value sum{ product(r) };
        u32 l{};
        for (u32 bit{ bitWidth_ } ; bit ; ) {
            bit--;
            u32 nxt{ l | (1u << bit) };
            if (nxt <= r and not f(Group::operation(Group::inverse(dat_[nxt]), sum))) {
                sum = Group::operation(Group::inverse(dat_[nxt]), sum);
                l = std::move(nxt);
            }
        }
        assert(l <= r);
        return l;
    }

    // debug print
    friend std::ostream& operator<<(std::ostream& os, const FenwickTree& ft) {
        for (u32 i{} ; i <= ft.size() ; i++) {
            os << ft.prefixProduct(i) << (i == ft.size() ? "" : " ");
        }
        return os;
    }

};


} // namespace zawa

namespace zawa {

template <class T>
class AdditiveGroup {
public:
    using Element = T;
    static constexpr T identity() noexcept {
        return T{};
    }
    static constexpr T operation(const T& l, const T& r) noexcept {
        return l + r;
    }
    static constexpr T inverse(const T& v) noexcept {
        return -v;
    }
};

} // namespace zawa
using namespace zawa;

int main() {
    SetFastIO();

    int n, m, k; std::cin >> n >> m >> k;
    std::vector<int> s(k + 1);
    for (int i{} ; i < k + 1 ; i++) {
        std::cin >> s[i];
        s[i]--;
    }
    const long long INF{(long long)1e18};
    std::vector g(n, std::vector<long long>(n, INF));
    for (int i{} ; i < n ; i++) g[i][i] = 0;
    for (int _{} ; _ < m ; _++) {
        int u, v; std::cin >> u >> v;
        u--; v--;
        long long c; std::cin >> c;
        g[u][v] = std::min(g[u][v], c);
        g[v][u] = std::min(g[v][u], c);
    }
    for (int v{} ; v < n ; v++) {
        for (int i{} ; i < n ; i++) {
            for (int j{} ; j < n ; j++) {
                g[i][j] = std::min(g[i][v] + g[v][j], g[i][j]);
            }
        }
    }
    FenwickTree<AdditiveGroup<long long>> fen(k);
    for (int i{1} ; i < k + 1 ; i++) {
        fen.set(i - 1, g[s[i - 1]][s[i]]);
    }
    int q; std::cin >> q;
    for (int _{} ; _ < q ; _++) {
        int t; std::cin >> t;
        if (t == 1) {
            int x, y; std::cin >> x >> y;
            y--;
            if (x) fen.set(x - 1, g[s[x - 1]][y]);
            if (x + 1 < k + 1) fen.set(x, g[y][s[x + 1]]);
            s[x] = y;
        }
        else if (t == 2) {
            int x, y; std::cin >> x >> y;
            long long ans{fen.product(x, y)};
            std::cout << ans << '\n';
        }
        else {
            assert(!"input fail");
        }
    }
}
0