結果
問題 | No.2640 traO Stamps |
ユーザー | Aeren |
提出日時 | 2024-02-19 21:49:37 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 71 ms / 2,000 ms |
コード長 | 5,436 bytes |
コンパイル時間 | 3,338 ms |
コンパイル使用メモリ | 260,972 KB |
実行使用メモリ | 7,680 KB |
最終ジャッジ日時 | 2024-09-29 01:47:15 |
合計ジャッジ時間 | 7,562 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 34 |
ソースコード
// #pragma GCC optimize("O3,unroll-loops")#include <bits/stdc++.h>// #include <x86intrin.h>using namespace std;#if __cplusplus >= 202002Lusing namespace numbers;#endiftemplate<class T>struct floyd_warshall{int n;vector<vector<T>> dist;floyd_warshall(int n): n(n), dist(n, vector<T>(n)){ }// Assumes the graph has no negative cycle// O(|V|^3)template<class U>void run(const vector<vector<U>> &adjm){assert(!n && adjm.empty() || n == (int)adjm.size() && n == (int)adjm[0].size());for(auto u = 0; u < n; ++ u) for(auto v = 0; v < n; ++ v) dist[u][v] = adjm[u][v];for(auto w = 0; w < n; ++ w) for(auto u = 0; u < n; ++ u) for(auto v = 0; v < n; ++ v) dist[u][v] = min(dist[u][v], dist[u][w] + dist[w][v]);}template<class U>void run(const vector<tuple<int, int, U>> &edge, bool directed = false){vector<vector<T>> adjm(n, vector<T>(n, numeric_limits<T>::max() / 2));for(auto u = 0; u < n; ++ u) adjm[u][u] = 0;for(auto [u, v, w]: edge){adjm[u][v] = min<T>(adjm[u][v], w);if(!directed) adjm[v][u] = adjm[u][v];}run(adjm);}// Requires graphtemplate<class G>void run(const G &g, bool directed = false){vector<vector<T>> adjm(n, vector<T>(n, numeric_limits<T>::max() / 2));for(auto u = 0; u < n; ++ u) adjm[u][u] = 0;for(auto [u, v, w]: g.edge){adjm[u][v] = min<T>(adjm[u][v], w);if(!directed) adjm[v][u] = adjm[u][v];}run(adjm);}};template<bool ALLOW_NON_PREFIX_QUERY, class T, class F, class I>struct fenwick_tree{int n;vector<T> data;F TT;T T_id;I Tinv;fenwick_tree(F TT, T T_id, I Tinv): TT(TT), T_id(T_id), Tinv(Tinv){ }fenwick_tree &operator=(const fenwick_tree &fw){n = fw.n;data = fw.data;}// O(n)void build(int n){this->n = n;data.assign(n, T_id);}// O(n)void build(int n, T x){this->n = n;data.assign(n, x);for(auto i = 1; i <= n; ++ i) if(i + (i & -i) <= n) data[i + (i & -i) - 1] = TT(data[i + (i & -i) - 1], data[i - 1]);}// O(n)template<class U>void build(const vector<U> &a){n = (int)a.size();data.resize(n);copy(a.begin(), a.end(), data.begin());for(auto i = 1; i <= n; ++ i) if(i + (i & -i) <= n) data[i + (i & -i) - 1] = TT(data[i + (i & -i) - 1], data[i - 1]);}// O(log(n))void update(int p, T x){assert(0 <= p && p < n);for(++ p; p <= n; p += p & -p) data[p - 1] = TT(data[p - 1], x);}// O(log(n))T prefix(int r) const{T s = T_id;for(; r > 0; r -= r & -r) s = TT(s, data[r - 1]);return s;}// O(log(n))T query(int l, int r) const{static_assert(ALLOW_NON_PREFIX_QUERY);assert(0 <= l && l <= r && r <= n);if(l == r) return T_id;T sum_minus = T_id, sum_plus = T_id;for(; l < r; r -= r & -r) sum_plus = TT(sum_plus, data[r - 1]);for(; r < l; l -= l & -l) sum_minus = TT(sum_minus, data[l - 1]);return TT(sum_plus, Tinv(sum_minus));}// O(log(n))T query(int p) const{static_assert(ALLOW_NON_PREFIX_QUERY);return query(p, p + 1);}// pred(sum[0, r)) is T, T, ..., T, F, F, ..., F, returns max r with T// O(log(n))int max_pref(auto pred) const{assert(pred(T_id));int p = 0;T sum = T_id;for(auto i = __lg(n + 1); i >= 0; -- i) if(p + (1 << i) <= n && pred(TT(sum, data[p + (1 << i) - 1]))){sum = TT(sum, data[p + (1 << i) - 1]);p += 1 << i;}return p;}template<class output_stream>friend output_stream &operator<<(output_stream &out, const fenwick_tree &fw){out << "{";for(auto i = 0; i < fw.n; ++ i){out << fw.query(i);if(i != fw.n - 1) out << ", ";}return out << '}';}};template<class T, class F, class I>auto make_fenwick_tree(F TT, T T_id, I Tinv){return fenwick_tree<true, T, F, I>(TT, T_id, Tinv);}template<class T>auto make_fenwick_tree_sum(){return fenwick_tree<true, T, plus<>, negate<>>(plus<>(), T{0}, negate<>());}template<class T>auto make_fenwick_tree_product(){auto inverse = [](const T &x){ return 1 / x; };return fenwick_tree<true, T, multiplies<>, decltype(inverse)>(multiplies<>(), T{1}, inverse);}template<class T>auto make_fenwick_tree_min(){auto TT = [&](const T &x, const T &y)->T{ return min(x, y); };return fenwick_tree<false, T, decltype(TT), negate<>>(TT, numeric_limits<T>::max(), negate<>());}template<class T>auto make_fenwick_tree_max(){auto TT = [&](const T &x, const T &y)->T{ return max(x, y); };return fenwick_tree<false, T, decltype(TT), negate<>>(TT, numeric_limits<T>::max(), negate<>());}int main(){cin.tie(0)->sync_with_stdio(0);cin.exceptions(ios::badbit | ios::failbit);int n, m, k;cin >> n >> m >> k;vector<int> pos(k + 1);vector<tuple<int, int, int>> edge(m);for(auto &u: pos){cin >> u, -- u;}for(auto &[u, v, w]: edge){cin >> u >> v >> w, -- u, -- v;}floyd_warshall<long long> floyd(n);floyd.run(edge);vector<long long> init(k);for(auto i = 0; i < k; ++ i){init[i] = floyd.dist[pos[i]][pos[i + 1]];}auto fw = make_fenwick_tree_sum<long long>();fw.build(init);int qn;cin >> qn;for(auto qi = 0; qi < qn; ++ qi){int type;cin >> type;if(type == 1){int i, u;cin >> i >> u, -- u;if(i > 0){fw.update(i - 1, floyd.dist[pos[i - 1]][u] - floyd.dist[pos[i - 1]][pos[i]]);}if(i < k){fw.update(i, floyd.dist[u][pos[i + 1]] - floyd.dist[pos[i]][pos[i + 1]]);}pos[i] = u;}else{int ql, qr;cin >> ql >> qr;cout << fw.query(ql, qr) << "\n";}}return 0;}/**/