結果

問題 No.2640 traO Stamps
コンテスト
ユーザー InTheBloom
提出日時 2024-02-19 23:26:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 285 ms / 2,000 ms
コード長 3,268 bytes
コンパイル時間 1,324 ms
コンパイル使用メモリ 118,120 KB
実行使用メモリ 8,896 KB
最終ジャッジ日時 2024-09-29 03:10:14
合計ジャッジ時間 10,824 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;
using ll = long long;

constexpr ll INF = 1'000'000'000'000'000'000;

class SegmentTree_RSQ {
    // segment tree RSQ
    private:
        vector<ll> A;
        int N;
        int len;

        // Monoid
        ll e = 0;
        function<ll(ll, ll)> op = [](ll x, ll y) {
            return x + y;
        };

    public:
        SegmentTree_RSQ (int N_) {
            N = N_;
            len = 1;
            while (len < N) len *= 2;
            A.resize(2*len);
            for (int i = 0; i < A.size(); i++) A[i] = e;
        }

        void set (int i, ll val) {
            assert(0 <= i && i < N);
            A[len + i] = val;
            int cur = len + i;
            do {
                cur /= 2;
                A[cur] = op(A[2*cur], A[2*cur + 1]);
            } while (1 < cur);
        }

        ll get (int i) {
            assert(0 <= i && i < N);
            return A[len + i];
        }

        ll prod (int l, int r) {
            assert(0 <= l && l < N);
            assert(0 <= r && r <= N);
            assert(l <= r);

            r--; // closed lnterval
            l += len;
            r += len;

            ll res = e;
            while (l <= r) {
                if (l % 2 == 1) {
                    res = op(A[l], res);
                    l++;
                }
                l /= 2;

                if (r % 2 == 0) {
                    res = op(res, A[r]);
                    r--;
                }
                r /= 2;
            }

            return res;
        }
};

int main () {
    int N, M, K; cin >> N >> M >> K;
    vector<int> S(K+1);
    for (int i = 0; i < K+1; i++) cin >> S[i];
    for (int i = 0; i < K+1; i++) S[i]--;

    vector<vector<ll>> graph_mat(N, vector<ll>(N, INF));

    for (int i = 0; i < M; i++) {
        int A, B, C; cin >> A >> B >> C;
        A--, B--;
        graph_mat[A][B] = graph_mat[B][A] = C;
    }

    // floyd-warshall
    vector<vector<ll>> dist(N, vector<ll>(N));
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        if (i == j) {
            dist[i][j] = 0;
        }
        else {
            dist[i][j] = graph_mat[i][j];
        }
    }

    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
            if (dist[i][k] == INF || dist[k][j] == INF) continue;
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }

    // スタンプx -> x+1を押すために必要な最小距離をセグ木に載せる
    SegmentTree_RSQ RSQ(K);
    for (int i = 0; i < K; i++) {
        RSQ.set(i, dist[S[i]][S[i+1]]);
    }

    // クエリ処理
    int Q; cin >> Q;
    for (int i = 0; i < Q; i++) {
        int T, X, Y; cin >> T >> X >> Y;

        if (T == 1) {
            Y--;
            S[X] = Y;
            if (X < K) {
                RSQ.set(X, dist[S[X]][S[X+1]]);
            }
            if (0 < X) {
                RSQ.set(X-1, dist[S[X-1]][S[X]]);
            }
        }

        if (T == 2) {
            if (X == K) {
                cout << 0 << "\n";
            }
            else {
                cout << RSQ.prod(X, Y) << "\n";
            }
        }
    }
}
0