#380231 (C++14) No.899 γatheree

提出ソース

結果

問題	No.899 γatheree
ユーザー	polylogK
提出日時	2019-09-17 23:46:30
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	371 ms / 2,000 ms
コード長	5,040 bytes
コンパイル時間	1,802 ms
コンパイル使用メモリ	187,640 KB
実行使用メモリ	19,072 KB
最終ジャッジ日時	2024-07-07 13:54:39
合計ジャッジ時間	8,591 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	278 ms 18,816 KB
testcase_07	AC	280 ms 18,688 KB
testcase_08	AC	274 ms 18,700 KB
testcase_09	AC	293 ms 18,688 KB
testcase_10	AC	297 ms 18,816 KB
testcase_11	AC	285 ms 18,816 KB
testcase_12	AC	277 ms 18,688 KB
testcase_13	AC	272 ms 18,656 KB
testcase_14	AC	282 ms 18,580 KB
testcase_15	AC	283 ms 18,760 KB
testcase_16	AC	273 ms 18,644 KB
testcase_17	AC	275 ms 18,816 KB
testcase_18	AC	278 ms 18,816 KB
testcase_19	AC	278 ms 18,688 KB
testcase_20	AC	284 ms 18,688 KB
testcase_21	AC	371 ms 18,944 KB
testcase_22	AC	348 ms 19,072 KB
testcase_23	AC	343 ms 18,944 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename Monoid, typename OperatorMonoid = Monoid>
class lazy_segment_tree {
	using value_type = Monoid;
	using operator_type = OperatorMonoid;
	using size_type = size_t;

	using F = std::function<value_type (value_type, value_type)>;
	using G = std::function<value_type (value_type, operator_type, int, int)>;
	using H = std::function<operator_type (operator_type, operator_type)>;
	
	size_type size_;
	size_type height_;

	F f;
	G g;
	H h;
	value_type id;
	operator_type id_op;
	std::vector<value_type> data;
	std::vector<operator_type> lazy;
	std::vector<size_type> depth;
	
	const size_type get_height(const size_type& size) const {
		size_type height = 1;
		while(1 << height < size) height++;
		return height;
	}
	const size_type base_size() const {
		return 1 << height_;
	}
	const value_type reflect(const size_type & k) {
		if(lazy[k] == id_op) return data[k];
		int l = (k - (1 << depth[k])) * (base_size() >> depth[k]);
		int r = l + (base_size() >> depth[k]);
		return g(data[k], lazy[k], l, r);
	}
	void eval(const size_type & k) {
		if(lazy[k] == id_op) return;
		lazy[k << 1 ^ 0] = h(lazy[k << 1 ^ 0], lazy[k]);
		lazy[k << 1 ^ 1] = h(lazy[k << 1 ^ 1], lazy[k]);
		data[k] = reflect(k);
		lazy[k] = id_op;
	}
	void thrust(const size_type & k) {
		for(int i = height_; i; i--) eval(k >> i);
	}
	void recalc(size_type k) {
		while(k >>= 1) data[k] = f(reflect(k << 1 ^ 0), reflect(k << 1 ^ 1));
	}
	
	public:
	lazy_segment_tree() {}
	lazy_segment_tree(int n, const F & f, const G & g, const H & h, const value_type & id, const operator_type & id_op) :
		size_(n), f(f), g(g), h(h), id(id), id_op(id_op) {
		height_ = get_height(size_);
		data.assign(base_size() << 1, id);
		lazy.assign(base_size() << 1, id_op);
		depth.assign(base_size() << 1, 0);
		for(int i = 0; i < height_ + 1; i++)
			for(int j = (1 << i); j < (1 << (i + 1)); j++) depth[j] = i;
	}
	void update(size_type a, size_type b, operator_type x) {
		thrust(a += base_size());
		thrust(b += base_size() - 1);
		for(size_type l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
			if(l & 1) lazy[l] = h(lazy[l], x), l++;
			if(r & 1) --r, lazy[r] = h(lazy[r], x);
		}
		recalc(a);
		recalc(b);
	}
	void change(size_type k, const value_type x) {
		thrust(k += base_size());
		data[k] = x;
		lazy[k] = id_op;
		recalc(k);
	}
	const value_type fold(size_type a, size_type b) {
		thrust(a += base_size());
		thrust(b += base_size() - 1);

		value_type left_value = id;
		value_type right_value = id;
		for(size_type l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
			if(l & 1) left_value = f(left_value, reflect(l++));
			if(r & 1) right_value = f(reflect(--r), right_value);
		}
		return f(left_value, right_value);
	}

	const value_type operator[](const size_type & k) {
		return fold(k, k + 1);
	}
};

int main() {
	int n; scanf("%d", &n);
	assert(2 <= n and n <= (int)1e5);
	
	std::vector<std::vector<int>> g(n);
	for(int i = 0; i < n - 1; i++) {
		int a, b; scanf("%d%d", &a, &b);

		assert(0 <= a and a < n);
		assert(0 <= b and b < n);
		
		g[a].push_back(b);
		g[b].push_back(a);
	}
	std::vector<i64> a(n);
	for(int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		
		assert(0 <= a[i] and a[i] <= (int)1e5);
	}

	int cnt = 1;
	std::queue<int> qu; qu.push(0);
	std::vector<int> vid(n), inv(n), par(n, -1), L(n), R(n), LL(n, n), RR(n, 0);
	while(!qu.empty()) {
		auto v = qu.front(); qu.pop();

		L[v] = cnt;
		if(par[v] != -1) LL[par[v]] = std::min(LL[par[v]], cnt);
		for(auto e: g[v]) {
			if(e == par[v]) continue;
			par[e] = v;
			vid[e] = cnt++;
			inv[vid[e]] = e;
			
			qu.push(e);
		}
		R[v] = cnt;
		if(par[v] != -1) RR[par[v]] = std::max(RR[par[v]], cnt);
	}

	auto f = [](i64 a, i64 b) { return a + b; };
	auto gg = [](i64 a, i64 b, int l, int r) { return b * (i64)(r - l); };
	auto h = [](i64 a, i64 b) { return b; };
	lazy_segment_tree<i64, i64> seg(n, f, gg, h, 0, -1);
	for(int i = 0; i < n; i++) seg.change(vid[i], a[i]);

	int q; scanf("%d", &q);
	assert(1 <= q and q <= (int)1e5);
	
	while(q--) {
		int v; scanf("%d", &v);
		assert(0 <= v and v < n);

		i64 A = seg[vid[v]];
		i64 B = seg.fold(L[v], R[v]);
		i64 C = seg.fold(LL[v], RR[v]);
		i64 D = (par[v] != -1 ? seg.fold(L[par[v]], R[par[v]]) - A : 0);
		i64 E = (par[v] != -1 ? seg[vid[par[v]]] : 0);
		i64 F = (par[v] != -1 and par[par[v]] != -1 ? seg[vid[par[par[v]]]] : 0);

		if(par[v] != -1 and par[par[v]] != -1) seg.change(vid[par[par[v]]], 0);
		if(par[v] != -1) seg.change(vid[par[v]], 0);
		if(par[v] != -1) seg.update(L[par[v]], R[par[v]], 0);
		seg.change(vid[v], A + B + C + D + E + F);
		seg.update(L[v], R[v], 0);
		seg.update(LL[v], RR[v], 0);

		printf("%lld\n", A + B + C + D + E + F);
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード