結果

問題 No.2640 traO Stamps
ユーザー InTheBloomInTheBloom
提出日時 2024-02-19 23:26:49
言語 C++23
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 232 ms
8,448 KB
testcase_07 AC 254 ms
8,184 KB
testcase_08 AC 268 ms
8,720 KB
testcase_09 AC 229 ms
6,820 KB
testcase_10 AC 244 ms
8,580 KB
testcase_11 AC 218 ms
6,816 KB
testcase_12 AC 245 ms
8,540 KB
testcase_13 AC 205 ms
6,820 KB
testcase_14 AC 258 ms
8,640 KB
testcase_15 AC 237 ms
6,816 KB
testcase_16 AC 220 ms
8,408 KB
testcase_17 AC 229 ms
8,644 KB
testcase_18 AC 249 ms
6,816 KB
testcase_19 AC 256 ms
8,508 KB
testcase_20 AC 248 ms
8,628 KB
testcase_21 AC 228 ms
6,820 KB
testcase_22 AC 264 ms
8,636 KB
testcase_23 AC 236 ms
6,820 KB
testcase_24 AC 239 ms
6,816 KB
testcase_25 AC 250 ms
8,608 KB
testcase_26 AC 240 ms
8,896 KB
testcase_27 AC 247 ms
8,740 KB
testcase_28 AC 235 ms
8,792 KB
testcase_29 AC 271 ms
8,796 KB
testcase_30 AC 285 ms
8,728 KB
testcase_31 AC 282 ms
8,736 KB
testcase_32 AC 268 ms
8,588 KB
testcase_33 AC 267 ms
8,596 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