結果

問題 No.2640 traO Stamps
ユーザー InTheBloomInTheBloom
提出日時 2024-02-19 23:24:58
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 3,156 bytes
コンパイル時間 1,160 ms
コンパイル使用メモリ 117,592 KB
実行使用メモリ 8,876 KB
最終ジャッジ日時 2024-02-19 23:25:10
合計ジャッジ時間 10,664 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 RE -
testcase_02 AC 2 ms
6,676 KB
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 AC 206 ms
8,620 KB
testcase_07 AC 229 ms
8,344 KB
testcase_08 AC 236 ms
8,680 KB
testcase_09 AC 207 ms
6,676 KB
testcase_10 AC 251 ms
8,740 KB
testcase_11 AC 192 ms
6,676 KB
testcase_12 AC 222 ms
8,600 KB
testcase_13 AC 189 ms
6,676 KB
testcase_14 AC 235 ms
8,780 KB
testcase_15 AC 236 ms
6,676 KB
testcase_16 AC 207 ms
8,524 KB
testcase_17 AC 210 ms
8,644 KB
testcase_18 AC 220 ms
6,676 KB
testcase_19 AC 229 ms
8,736 KB
testcase_20 AC 224 ms
8,748 KB
testcase_21 AC 203 ms
6,676 KB
testcase_22 AC 238 ms
8,792 KB
testcase_23 AC 212 ms
6,676 KB
testcase_24 AC 247 ms
6,676 KB
testcase_25 AC 222 ms
8,744 KB
testcase_26 AC 230 ms
8,836 KB
testcase_27 AC 233 ms
8,836 KB
testcase_28 AC 218 ms
8,836 KB
testcase_29 AC 272 ms
8,836 KB
testcase_30 AC 261 ms
8,876 KB
testcase_31 AC 277 ms
8,772 KB
testcase_32 AC 237 ms
8,756 KB
testcase_33 AC 266 ms
8,708 KB
権限があれば一括ダウンロードができます

ソースコード

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) {
            cout << RSQ.prod(X, Y) << "\n";
        }
    }
}
0