結果

問題 No.2640 traO Stamps
ユーザー InTheBloomInTheBloom
提出日時 2024-02-19 23:26:49
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 273 ms / 2,000 ms
コード長 3,268 bytes
コンパイル時間 1,088 ms
コンパイル使用メモリ 117,340 KB
実行使用メモリ 8,876 KB
最終ジャッジ日時 2024-02-19 23:27:01
合計ジャッジ時間 10,131 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 1 ms
6,676 KB
testcase_02 AC 1 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 1 ms
6,676 KB
testcase_05 AC 2 ms
6,676 KB
testcase_06 AC 200 ms
8,620 KB
testcase_07 AC 244 ms
8,344 KB
testcase_08 AC 238 ms
8,680 KB
testcase_09 AC 203 ms
6,676 KB
testcase_10 AC 219 ms
8,740 KB
testcase_11 AC 199 ms
6,676 KB
testcase_12 AC 246 ms
8,600 KB
testcase_13 AC 188 ms
6,676 KB
testcase_14 AC 230 ms
8,780 KB
testcase_15 AC 206 ms
6,676 KB
testcase_16 AC 197 ms
8,524 KB
testcase_17 AC 229 ms
8,644 KB
testcase_18 AC 215 ms
6,676 KB
testcase_19 AC 228 ms
8,736 KB
testcase_20 AC 221 ms
8,748 KB
testcase_21 AC 203 ms
6,676 KB
testcase_22 AC 249 ms
8,792 KB
testcase_23 AC 205 ms
6,676 KB
testcase_24 AC 222 ms
6,676 KB
testcase_25 AC 221 ms
8,744 KB
testcase_26 AC 223 ms
8,836 KB
testcase_27 AC 254 ms
8,836 KB
testcase_28 AC 216 ms
8,836 KB
testcase_29 AC 240 ms
8,836 KB
testcase_30 AC 254 ms
8,876 KB
testcase_31 AC 273 ms
8,772 KB
testcase_32 AC 231 ms
8,756 KB
testcase_33 AC 233 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) {
            if (X == K) {
                cout << 0 << "\n";
            }
            else {
                cout << RSQ.prod(X, Y) << "\n";
            }
        }
    }
}
0