結果

問題 No.2640 traO Stamps
ユーザー zawakasu
提出日時 2024-02-19 22:09:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 66 ms / 2,000 ms
コード長 6,281 bytes
コンパイル時間 1,881 ms
コンパイル使用メモリ 203,084 KB
最終ジャッジ日時 2025-02-19 17:03:50
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

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");
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0