結果
問題 | No.2640 traO Stamps |
ユーザー |
|
提出日時 | 2024-02-19 22:17:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 74 ms / 2,000 ms |
コード長 | 2,564 bytes |
コンパイル時間 | 4,324 ms |
コンパイル使用メモリ | 233,628 KB |
実行使用メモリ | 10,744 KB |
最終ジャッジ日時 | 2024-09-29 02:12:40 |
合計ジャッジ時間 | 7,719 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using P = pair<ll, ll>;using T = tuple<ll, ll, ll>;#include <atcoder/all>using namespace atcoder;// using mint = modint998244353;// using mint = modint1000000007;#define rep(i, n) for(ll i = 0; i < n; i++)#define reps(i, l, r) for(ll i = l; i < r; i++)template<typename S,S(*op)(S,S),S(*e)()>struct SegmentTree{SegmentTree() : n(0){}explicit SegmentTree(ll _n){n = _n;log2 = 0;while((1LL << log2) < n)log2++;size = 1LL << log2;data = vector<S>(2*size,e());}void set(ll i,S x){i += size;data[i] = x;while(i > 1) {i /= 2;update(i);}}void update(ll i) { data[i] = op(data[2*i],data[2*i+1]); }S all_prod() { return data[1]; }S prod(ll l,ll r){l += size, r += size;S sml = e(),smr = e();while( l < r ) {if( l & 1 ) sml = op(sml,data[l++]);if( r & 1 ) smr = op(data[--r],smr);l /= 2, r /= 2;}return op(sml,smr);}private:ll n, log2, size;vector<S> data;};// SegTree に乗せる型using S = ll;// operator (作用素)S op(S l,S r) {return l+r;}// 単位元 (op(e,a) = a)S e() {return 0;}int main() {cin.tie(nullptr);ios_base::sync_with_stdio(false);ll n, m, k; cin >> n >> m >> k;vector<ll> s(k+1);vector<vector<ll>> worshall(n, vector<ll>(n, 1e16));rep(i,k+1) {cin >> s[i];s[i]--;}rep(i,m) {ll a, b, c; cin >> a >> b >> c; a--; b--;worshall[a][b] = c;worshall[b][a] = c;}rep(i,n) worshall[i][i] = 0;rep(k,n) rep(i,n) rep(j,n) worshall[i][j] = min(worshall[i][j], worshall[i][k]+worshall[k][j]);segtree<S,op,e> seg(k);rep(i,k) seg.set(i, worshall[s[i]][s[i+1]]);ll q; cin >> q;while( q-- ) {ll t, x, y; cin >> t >> x >> y;if( t == 1 ) {y--;if( x != 0 ) {seg.set(x-1, worshall[s[x-1]][y]);// cerr << s[x-1] << endl;// rep(i,k) cerr << seg.prod(i,i+1) << " \n"[i==k-1];}if( x != k ) {seg.set(x, worshall[y][s[x+1]]);// cerr << s[x+1] << endl;// rep(i,k) cerr << seg.prod(i,i+1) << " \n"[i==k-1];}s[x] = y;}else cout << seg.prod(x,y) << '\n';}return 0;}