結果

問題 No.2640 traO Stamps
ユーザー shogo314shogo314
提出日時 2024-02-19 22:11:15
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 66 ms / 2,000 ms
コード長 16,800 bytes
コンパイル時間 3,229 ms
コンパイル使用メモリ 258,540 KB
実行使用メモリ 10,924 KB
最終ジャッジ日時 2024-02-19 22:11:23
合計ジャッジ時間 7,761 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,676 KB
testcase_01 AC 1 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 2 ms
6,676 KB
testcase_05 AC 1 ms
6,676 KB
testcase_06 AC 55 ms
10,016 KB
testcase_07 AC 54 ms
9,756 KB
testcase_08 AC 61 ms
10,548 KB
testcase_09 AC 48 ms
7,296 KB
testcase_10 AC 57 ms
10,512 KB
testcase_11 AC 59 ms
7,552 KB
testcase_12 AC 56 ms
10,560 KB
testcase_13 AC 57 ms
7,552 KB
testcase_14 AC 60 ms
10,600 KB
testcase_15 AC 53 ms
7,680 KB
testcase_16 AC 51 ms
10,332 KB
testcase_17 AC 56 ms
10,364 KB
testcase_18 AC 53 ms
7,680 KB
testcase_19 AC 61 ms
10,644 KB
testcase_20 AC 57 ms
10,652 KB
testcase_21 AC 50 ms
7,680 KB
testcase_22 AC 63 ms
10,716 KB
testcase_23 AC 52 ms
7,424 KB
testcase_24 AC 54 ms
7,552 KB
testcase_25 AC 58 ms
10,768 KB
testcase_26 AC 48 ms
10,924 KB
testcase_27 AC 54 ms
10,924 KB
testcase_28 AC 47 ms
10,924 KB
testcase_29 AC 51 ms
10,924 KB
testcase_30 AC 66 ms
10,700 KB
testcase_31 AC 64 ms
10,812 KB
testcase_32 AC 63 ms
10,236 KB
testcase_33 AC 62 ms
10,412 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 2 "/home/shogo314/cpp_include/ou-library/io.hpp"
/**
 * @file io.hpp
 * @brief 空白区切り出力、iostreamのオーバーロード
 */

#include <array>
#include <iostream>
#include <utility>
#include <tuple>
#include <vector>

namespace tuple_io {
    template <typename Tuple, size_t I, typename CharT, typename Traits>
    std::basic_istream<CharT, Traits>& read_tuple(std::basic_istream<CharT, Traits>& is, Tuple& t) {
        is >> std::get<I>(t);
        if constexpr (I + 1 < std::tuple_size_v<Tuple>) {
            return read_tuple<Tuple, I + 1>(is, t);
        }
        return is;
    }
    template <typename Tuple, size_t I, typename CharT, typename Traits>
    std::basic_ostream<CharT, Traits>& write_tuple(std::basic_ostream<CharT, Traits>& os, const Tuple& t) {
        os << std::get<I>(t);
        if constexpr (I + 1 < std::tuple_size_v<Tuple>) {
            os << CharT(' ');
            return write_tuple<Tuple, I + 1>(os, t);
        }
        return os;
    }
};

template <typename T1, typename T2, typename CharT, typename Traits>
std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}
template <typename... Types, typename CharT, typename Traits>
std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::tuple<Types...>& p) {
    return tuple_io::read_tuple<std::tuple<Types...>, 0>(is, p);
}
template <typename T, size_t N, typename CharT, typename Traits>
std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::array<T, N>& a) {
    for(auto& e : a) is >> e;
    return is;
}
template <typename T, typename CharT, typename Traits>
std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::vector<T>& v) {
    for(auto& e : v) is >> e;
    return is;
}

template <typename T1, typename T2, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::pair<T1, T2>& p) {
    os << p.first << CharT(' ') << p.second;
    return os;
}
template <typename... Types, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::tuple<Types...>& p) {
    return tuple_io::write_tuple<std::tuple<Types...>, 0>(os, p);
}
template <typename T, size_t N, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::array<T, N>& a) {
    for(size_t i = 0; i < N; ++i) {
        if(i) os << CharT(' ');
        os << a[i];
    }
    return os;
}
template <typename T, typename CharT, typename Traits>
std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::vector<T>& v) {
    for(size_t i = 0; i < v.size(); ++i) {
        if(i) os << CharT(' ');
        os << v[i];
    }
    return os;
}

/**
 * @brief 空行出力
 */
void print() { std::cout << '\n'; }
/**
 * @brief 出力して改行
 * 
 * @tparam T 型
 * @param x 出力する値
 */
template <typename T>
void print(const T& x) { std::cout << x << '\n'; }
/**
 * @brief 空白区切りで出力して改行
 * 
 * @tparam T 1つ目の要素の型
 * @tparam Tail 2つ目以降の要素の型
 * @param x 1つ目の要素
 * @param tail 2つ目以降の要素
 */
template <typename T, typename... Tail>
void print(const T& x, const Tail&... tail) {
    std::cout << x << ' ';
    print(tail...);
}
#line 2 "/home/shogo314/cpp_include/ou-library/segtree.hpp"

/**
 * @file segtree.hpp
 * @brief セグメント木
 */

#include <cassert>
#include <functional>
#include <limits>
#include <ostream>
#line 13 "/home/shogo314/cpp_include/ou-library/segtree.hpp"

/**
 * @brief セグメント木のCRTP基底クラス
 * 
 * @tparam S モノイドの型
 * @tparam ActualSegTree 派生クラス
 */
template <typename S, typename ActualSegTree>
class SegTreeBase {
    S op(const S& a, const S& b) const { return static_cast<const ActualSegTree&>(*this).op(a, b); }
    S e() const { return static_cast<const ActualSegTree&>(*this).e(); }

    int n, sz, height;
    std::vector<S> data;
    void update(int k) { data[k] = op(data[2 * k], data[2 * k + 1]); }

    class SegTreeReference {
        SegTreeBase& segtree;
        int k;
    public:
        SegTreeReference(SegTreeBase& segtree, int k) : segtree(segtree), k(k) {}
        SegTreeReference& operator=(const S& x) {
            segtree.set(k, x);
            return *this;
        }
        operator S() const { return segtree.get(k); }
    };

protected:
    void construct_data() {
        sz = 1;
        height = 0;
        while (sz < n) {
            sz <<= 1;
            height++;
        }
        data.assign(sz * 2, e());
    }
    void initialize(const std::vector<S>& v) {
        for (int i = 0; i < n; i++) data[sz + i] = v[i];
        for (int i = sz - 1; i > 0; i--) update(i);
    }

public:
    // Warning: 継承先のコンストラクタでconstruct_data()を必ず呼び出す！
    SegTreeBase(int n = 0) : n(n) {}

    /**
     * @brief 指定された要素の値を返す
     * 
     * @param k インデックス
     * @return S 値
     */
    S get(int k) const { return data[sz + k]; }
    /**
     * @brief 指定された要素の値を返す
     * 
     * @param k インデックス
     * @return S 値
     */
    S operator[] (int k) const { return get(k); }
    /**
     * @brief 指定された要素への参照を返す
     * 
     * @param k 
     * @return SegTreeReference 要素への参照 代入されるとset()が呼ばれる
     */
    SegTreeReference operator[] (int k) { return SegTreeReference(*this, k); }

    /**
     * @brief 内容を出力する
     * 
     * @tparam CharT 出力ストリームの文字型
     * @tparam Traits 出力ストリームの文字型特性
     * @param os 出力ストリーム
     * @param rhs セグメント木
     * @return std::basic_ostream<CharT, Traits>& 出力ストリーム 
     */
    template <class CharT, class Traits>
    friend std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const SegTreeBase& rhs) {
        for(int i = 0; i < rhs.n; i++) {
            if(i != 0) os << CharT(' ');
            os << rhs[i];
        }
        return os;
    }

    /**
     * @brief 指定された要素の値をxに更新する
     * 
     * @param k インデックス
     * @param x 新しい値
     */
    void set(int k, const S& x) {
        k += sz;
        data[k] = x;
        for (int i = 1; i <= height; i++) update(k >> i);
    }
    /**
     * @brief 指定された要素の値にxを作用させる
     * 
     * @param k インデックス
     * @param x 作用素
     */
    void apply(int k, const S& x) { set(k, op(get(k), x)); }

    /**
     * @brief [l, r)の区間の総積を返す
     * 
     * @param l 半開区間の開始
     * @param r 半開区間の終端
     * @return S 総積
     */
    S prod(int l, int r) const {
        S left_prod = e(), right_prod = e();
        l += sz;
        r += sz;
        while (l < r) {
            if (l & 1) left_prod = op(left_prod, data[l++]);
            if (r & 1) right_prod = op(data[--r], right_prod);
            l >>= 1;
            r >>= 1;
        }
        return op(left_prod, right_prod);
    }
    /**
     * @brief すべての要素の総積を返す
     * 
     * @return S 総積
     */
    S all_prod() const { return data[1]; }

    /**
     * @brief (r = l or f(prod([l, r))) = true) and (r = n or f(prod([l, r+1))) = false)となるrを返す
     * fが単調なら、f(prod([l, r))) = trueとなる最大のr
     * 
     * @tparam F
     * @param l 半開区間の開始
     * @param f 判定関数 f(e) = true
     * @return int
     */
    template <typename F>
    int max_right(int l, F f) const {
        assert(f(e()));
        if (l == n) return n;
        l += sz;
        while (l % 2 == 0) l >>= 1;
        S sum = e();
        while(f(op(sum, data[l]))) {
            sum = op(sum, data[l]);
            l++;
            while (l % 2 == 0) l >>= 1;
            if (l == 1) return n;
        }
        while (l < sz) {
            if (!f(op(sum, data[l * 2]))) l *= 2;
            else {
                sum = op(sum, data[l * 2]);
                l = l * 2 + 1;
            }
        }
        return l - sz;
    }
    /**
     * @brief (l = 0 or f(prod([l, r))) = true) and (l = r or f(prod([l-1, r))) = false)となるlを返す
     * fが単調なら、f(prod([l, r))) = trueとなる最小のl
     * 
     * @tparam F
     * @param r 半開区間の終端
     * @param f 判定関数 f(e) = true
     * @return int
     */
    template <typename F>
    int min_left(int r, F f) const {
        assert(f(e()));
        if (r == 0) return 0;
        r += sz;
        while (r % 2 == 0) r >>= 1;
        S sum = e();
        while(f(op(data[r-1], sum))) {
            sum = op(data[r-1], sum);
            r--;
            while (r % 2 == 0) r >>= 1;
            if (r == 1) return 0;
        }
        while (r < sz) {
            if (!f(op(data[r * 2 - 1], sum))) r *= 2;
            else {
                sum = op(data[r * 2 - 1], sum);
                r = r * 2 - 1;
            }
        }
        return r - sz;
    }
};

/**
 * @brief 積のファンクタが静的な場合のセグメント木の実装
 * 
 * @tparam S モノイドの型
 * @tparam Op 積のファンクタ
 * @tparam E 積の単位元を返すファンクタ
 */
template <typename S, typename Op, typename E>
class StaticSegTree : public SegTreeBase<S, StaticSegTree<S, Op, E>> {
    using BaseType = SegTreeBase<S, StaticSegTree<S, Op, E>>;

    inline static Op operator_object;
    inline static E identity_object;
public:
    S op(const S& a, const S& b) const { return operator_object(a, b); }
    S e() const { return identity_object(); }

    /**
     * @brief デフォルトコンストラクタ
     * 
    */
    StaticSegTree() = default;
    /**
     * @brief コンストラクタ
     * 
     * @param n 要素数
     */
    explicit StaticSegTree(int n) : BaseType(n) {
        this->construct_data();
    }
    /**
     * @brief コンストラクタ
     * 
     * @param v 初期の要素
     */
    explicit StaticSegTree(const std::vector<S>& v) : StaticSegTree(v.size()) {
        this->initialize(v);
    }
};

/**
 * @brief コンストラクタで関数オブジェクトを与えることで積を定義するセグメント木の実装
 * テンプレート引数を省略することができ、ラムダ式が使える
 * 
 * @tparam S モノイドの型
 * @tparam Op 積の関数オブジェクトの型
 */
template <typename S, typename Op>
class SegTree : public SegTreeBase<S, SegTree<S, Op>> {
    using BaseType = SegTreeBase<S, SegTree<S, Op>>;

    Op operator_object;
    S identity;

public:
    S op(const S& a, const S& b) const { return operator_object(a, b); }
    S e() const { return identity; }

    /**
     * @brief デフォルトコンストラクタ
    */
    SegTree() = default;
    /**
     * @brief コンストラクタ
     * 
     * @param n 要素数
     * @param op 積の関数オブジェクト
     * @param identity 単位元
     */
    explicit SegTree(int n, Op op, const S& identity) : BaseType(n), operator_object(std::move(op)), identity(identity) {
        this->construct_data();
    }
    /**
     * @brief コンストラクタ
     * 
     * @param v 初期の要素
     * @param op 積の関数オブジェクト
     * @param identity 単位元
     */
    explicit SegTree(const std::vector<S>& v, Op op, const S& identity) : SegTree(v.size(), std::move(op), identity) {
        this->initialize(v);
    }
};

namespace segtree {
    template <typename S>
    struct Max {
        const S operator() (const S& a, const S& b) const { return std::max(a, b); }
    };
    template <typename S>
    struct Min {
        const S operator() (const S& a, const S& b) const { return std::min(a, b); }
    };
    template <typename S, std::enable_if_t<std::is_scalar_v<S>>* = nullptr>
    struct MaxLimit {
        constexpr S operator() () const { return std::numeric_limits<S>::max(); }
    };
    template <typename S, std::enable_if_t<std::is_scalar_v<S>>* = nullptr>
    struct MinLimit {
        constexpr S operator() () const { return std::numeric_limits<S>::lowest(); }
    };
    template <typename S>
    struct Zero {
        S operator() () const { return S(0); }
    };
}
/**
 * @brief RangeMaxQuery
 * 
 * @tparam S 型
 */
template <typename S>
using RMaxQ = StaticSegTree<S, segtree::Max<S>, segtree::MinLimit<S>>;
/**
 * @brief RangeMinQuery
 * 
 * @tparam S 型
 */
template <typename S>
using RMinQ = StaticSegTree<S, segtree::Min<S>, segtree::MaxLimit<S>>;
/**
 * @brief RangeSumQuery
 * 
 * @tparam S 型
 */
template <typename S>
using RSumQ = StaticSegTree<S, std::plus<S>, segtree::Zero<S>>;
#line 1 "/home/shogo314/cpp_include/sh-library/base.hpp"
#include <bits/stdc++.h>

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;
using ll = long long;
using ull = unsigned long long;
using str = string;
using pl = pair<ll, ll>;
template <typename T>
using ml = map<ll, T>;
using mll = map<ll, ll>;
using sl = set<ll>;
using ld = long double;
using pd = pair<ld, ld>;
template <typename T>
using vec = vector<T>;
template <typename T>
using vv = vector<vector<T>>;
template <typename T>
using vvv = vector<vector<vector<T>>>;
template <typename T1, typename T2>
using vp = vector<pair<T1, T2>>;
using vl = vec<ll>;
using vvl = vv<ll>;
using vvvl = vvv<ll>;
using vs = vec<str>;
using vc = vec<char>;
using vi = vec<int>;
using vb = vec<bool>;
using vpl = vec<pl>;
using spl = set<pl>;
using vd = vec<ld>;
using vpd = vec<pd>;
template <typename T, int N>
using ary = array<T, N>;
template <int N>
using al = array<ll, N>;
template <int N1, int N2>
using aal = array<array<ll, N2>, N1>;
template <int N>
using val = vec<al<N>>;

#define all(obj) (obj).begin(), (obj).end()

#define reps(i, a, n) for (ll i = (a); i < ll(n); i++)
#define rep(i, n) reps(i, 0, (n))
#define rrep(i, n) reps(i, 1, (n) + 1)
#define repds(i, a, n) for (ll i = ((n) - 1); i >= (a); i--)
#define repd(i, n) repds(i, 0, (n))
#define rrepd(i, n) repds(i, 1, (n) + 1)
#define rep2(i, j, x, y) rep(i, x) rep(j, y)

template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#define LL(x) ll x;cin >> x;
#define VL(a,n) vl a(n);cin >> a;
#define AL(a,k) al<k> a;cin >> a;
#define VC(a,n) vc a(n);cin >> a;
#define VS(a,n) vs a(n);cin >> a;
#define STR(s) str s;cin >> s;
#define VPL(a,n) vpl a(n);cin >> a;
#define VAL(a,n,k) val<k> a(n);cin >> a;
#define VVL(a,n,m) vvl a(n,vl(m));cin >> a;
#define SL(a,n) sl a;{VL(b,n);a=sl(all(b));}

template <typename T>
using heap_max = priority_queue<T, vec<T>, less<T>>;
template <typename T>
using heap_min = priority_queue<T, vec<T>, greater<T>>;
#line 4 "main.cpp"

void solve() {
    LL(N);
    LL(M);
    LL(K);
    VL(S, K + 1);
    rep(i, K + 1) {
        S[i]--;
    }
    vvl g(N, vl(N, 1LL << 61));
    rep(i, M) {
        LL(A);
        LL(B);
        LL(C);
        A--;
        B--;
        chmin(g[A][B], C);
        chmin(g[B][A], C);
    }
    rep(k, N) {
        rep(i, N) {
            rep(j, N) {
                chmin(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    rep(i, N) {
        g[i][i] = 0;
    }
    vl init(K);
    rep(i, K) {
        // cerr << "(" << S[i] << ", " << S[i + 1] << ")" << endl;
        init[i] = g[S[i]][S[i + 1]];
    }
    RSumQ<ll> seg(init);
    if (false) {
        cerr << "S = " << S << endl;
        cerr << "seg =";
        rep(i, K) {
            cerr << " " << seg[i];
        }
        cerr << endl;
    }
    LL(Q);
    while (Q--) {
        LL(T);
        LL(X);
        LL(Y);
        if (T == 1) {
            Y--;
            S[X] = Y;
            if (X > 0) {
                seg.set(X - 1, g[S[X - 1]][S[X]]);
            }
            if (X < K) {
                seg.set(X, g[S[X]][S[X + 1]]);
            }
        } else {
            print(seg.prod(X, Y));
        }
        if (false) {
            cerr << "S = " << S << endl;
            cerr << "seg =";
            rep(i, K) {
                cerr << " " << seg[i];
            }
            cerr << endl;
        }
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    solve();
}
0