#952695 (C++23) No.2640 traO Stamps

提出ソース
結果

問題	No.2640 traO Stamps
ユーザー	shogo314
提出日時	2024-02-19 21:54:06
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	WA
実行時間	-
コード長	16,424 bytes
コンパイル時間	2,959 ms
コンパイル使用メモリ	258,608 KB
実行使用メモリ	10,784 KB
最終ジャッジ日時	2024-09-29 01:52:32
合計ジャッジ時間	6,954 ms
ジャッジサーバーID （参考情報）	judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	WA * 33
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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 << 62));
    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) {
            if (i == k) continue;
            rep(j, N) {
                if (j == k) continue;
                if (i == j) continue;
                chmin(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    vl init(K);
    rep(i, K) {
        init[i] = g[S[i]][S[i + 1]];
    }
    RSumQ<ll> seg(init);
    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));
        }
    }
}

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

結果

ソースコード
