#952663 (C++23) No.2640 traO Stamps

提出ソース

結果

問題	No.2640 traO Stamps
ユーザー	Aeren
提出日時	2024-02-19 21:49:37
言語	C++23 (gcc 12.3.0 + boost 1.83.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
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,820 KB
testcase_06	AC	59 ms 6,820 KB
testcase_07	AC	57 ms 6,816 KB
testcase_08	AC	66 ms 7,168 KB
testcase_09	AC	52 ms 6,816 KB
testcase_10	AC	65 ms 7,140 KB
testcase_11	AC	52 ms 6,820 KB
testcase_12	AC	61 ms 7,168 KB
testcase_13	AC	52 ms 6,816 KB
testcase_14	AC	68 ms 7,296 KB
testcase_15	AC	56 ms 6,820 KB
testcase_16	AC	54 ms 7,040 KB
testcase_17	AC	59 ms 7,040 KB
testcase_18	AC	57 ms 6,816 KB
testcase_19	AC	65 ms 7,296 KB
testcase_20	AC	64 ms 7,424 KB
testcase_21	AC	54 ms 6,816 KB
testcase_22	AC	68 ms 7,296 KB
testcase_23	AC	54 ms 6,820 KB
testcase_24	AC	60 ms 6,816 KB
testcase_25	AC	64 ms 7,680 KB
testcase_26	AC	54 ms 7,552 KB
testcase_27	AC	55 ms 7,552 KB
testcase_28	AC	53 ms 7,552 KB
testcase_29	AC	58 ms 7,552 KB
testcase_30	AC	71 ms 7,672 KB
testcase_31	AC	71 ms 7,680 KB
testcase_32	AC	65 ms 7,036 KB
testcase_33	AC	67 ms 7,040 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif

template<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 graph
	template<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;
}

/*

*/

yukicoder

結果

テストケース

ソースコード