#279313 (C++14) No.399 動的な領主

提出ソース

結果

問題	No.399 動的な領主
ユーザー	noshi91
提出日時	2018-08-21 18:10:53
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	182 ms / 2,000 ms
コード長	7,532 bytes
コンパイル時間	1,003 ms
コンパイル使用メモリ	68,776 KB
実行使用メモリ	11,520 KB
最終ジャッジ日時	2024-05-09 16:25:19
合計ジャッジ時間	3,128 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	3 ms 5,376 KB
testcase_05	AC	14 ms 5,376 KB
testcase_06	AC	182 ms 11,392 KB
testcase_07	AC	181 ms 11,392 KB
testcase_08	AC	177 ms 11,392 KB
testcase_09	AC	165 ms 11,520 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	11 ms 5,376 KB
testcase_12	AC	108 ms 11,392 KB
testcase_13	AC	108 ms 11,392 KB
testcase_14	AC	24 ms 11,392 KB
testcase_15	AC	90 ms 11,392 KB
testcase_16	AC	103 ms 11,392 KB
testcase_17	AC	168 ms 11,392 KB
testcase_18	AC	172 ms 11,392 KB

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

ソースコード

raw source code

#define NDEBUG
#include <cassert>
#include <cstddef>
#include <memory>
#include <utility>
#include <vector>

template <class ValueSemigroup, class OperatorMonoid, class Modifier>
class lazy_st_trees {
public:
	using value_structure = ValueSemigroup;
	using value_type = typename value_structure::value_type;
	using operator_structure = OperatorMonoid;
	using operator_type = typename operator_structure::value_type;
	using modifier = Modifier;

private:
	class node_type {
	public:
		node_type *left, *right, *parent;
		typename lazy_st_trees::value_type value, sum;
		typename lazy_st_trees::operator_type lazy;
		bool reversed; // reverse->lazy
		template <class V>
		node_type(V &&v)
			: left(nullptr), right(nullptr), parent(nullptr),
			value(::std::forward<V>(v)), sum(value),
			lazy(operator_structure::identity()), reversed(0) {}
	};

	using container_type = ::std::vector<node_type>;

public:
	using size_type = typename container_type::size_type;

private:
	using pointer = node_type *;
	using const_pointer = const node_type *;

	static void reverse(const pointer ptr) {
		if (ptr) {
			ptr->lazy = operator_structure::reverse(::std::move(ptr->lazy));
			ptr->reversed ^= 1;
		}
	}
	static void act(const pointer ptr, const operator_type &value) {
		if (ptr)
			ptr->lazy = operator_structure::operation(::std::move(ptr->lazy), value);
	}
	static void push(const pointer ptr) {
		if (ptr->reversed) {
			ptr->reversed = 0;
			ptr->value = value_structure::reverse(::std::move(ptr->value));
			::std::swap(ptr->left, ptr->right);
			reverse(ptr->left);
			reverse(ptr->right);
		}
		act(ptr->left, ptr->lazy);
		act(ptr->right, ptr->lazy);
		ptr->value =
			modifier::operation(::std::move(ptr->value), ::std::move(ptr->lazy));
		ptr->lazy = operator_structure::identity();
	}
	static void propagate(pointer ptr) {
		pointer prev = nullptr;
		while (ptr) {
			::std::swap(ptr->parent, prev);
			::std::swap(ptr, prev);
		}
		while (prev) {
			push(prev);
			::std::swap(prev->parent, ptr);
			::std::swap(prev, ptr);
		}
	}
	static value_type reflect(const const_pointer ptr) {
		return modifier::operation(
			ptr->reversed ? value_structure::reverse(ptr->sum) : ptr->sum,
			ptr->lazy);
	}
	static void calc(const pointer ptr) {
		if (ptr->left) {
			if (ptr->right)
				ptr->sum = value_structure::operation(
					value_structure::operation(reflect(ptr->left), ptr->value),
					reflect(ptr->right));
			else
				ptr->sum = value_structure::operation(reflect(ptr->left), ptr->value);
		}
		else {
			if (ptr->right)
				ptr->sum = value_structure::operation(ptr->value, reflect(ptr->right));
			else
				ptr->sum = ptr->value;
		}
	}
	static void rotate_l(const pointer ptr, const pointer ch) {
		ptr->right = ch->left;
		if (ch->left)
			ch->left->parent = ptr;
		calc(ptr);
		ch->left = ptr;
		ptr->parent = ch;
	}
	static void rotate_r(const pointer ptr, const pointer ch) {
		ptr->left = ch->right;
		if (ch->right)
			ch->right->parent = ptr;
		calc(ptr);
		ch->right = ptr;
		ptr->parent = ch;
	}
	static void splay(const pointer ptr) {
		for (pointer x, y = ptr;;) {
			x = ptr->parent;
			if (!x) {
				return;
			}
			else if (x->left == y) {
				y = x->parent;
				if (!y)
					return ptr->parent = nullptr, rotate_r(x, ptr);
				else if (y->left == x)
					ptr->parent = y->parent, rotate_r(y, x), rotate_r(x, ptr);
				else if (y->right == x)
					ptr->parent = y->parent, rotate_l(y, ptr), rotate_r(x, ptr);
				else
					return ptr->parent = y, rotate_r(x, ptr);
			}
			else if (x->right == y) {
				y = x->parent;
				if (!y)
					return ptr->parent = y, rotate_l(x, ptr);
				if (y->right == x)
					ptr->parent = y->parent,  rotate_l(y, x), rotate_l(x, ptr);
				else if (y->left == x)
					ptr->parent = y->parent,  rotate_r(y, ptr), rotate_l(x, ptr);
				else
					return ptr->parent = y, rotate_l(x, ptr);
			}
			else {
				return;
			}
		}
	}
	static void expose(const pointer ptr) {
		propagate(ptr);
		pointer x = ptr, prev = nullptr;
		while (x) {
			splay(x);
			x->right = prev;
			calc(x);
			prev = x;
			x = x->parent;
		}
		splay(ptr);
		calc(ptr);
	}
	static void reroot(const pointer ptr) {
		expose(ptr);
		reverse(ptr);
	}

	container_type nodes;

	pointer get_ptr(const size_type v) { return nodes.data() + v; }

public:
	lazy_st_trees() : nodes() {}
	template <class InputIterator>
	lazy_st_trees(InputIterator first, InputIterator last) : nodes(first, last) {}

	bool empty() const { return nodes.empty(); }
	size_type size() const { return nodes.size(); }

	bool connected(const size_type v, const size_type u) {
		assert(v < size());
		assert(u < size());
		expose(get_ptr(v));
		expose(get_ptr(u));
		return nodes[v].parent || v == u;
	}
	value_type fold_path(const size_type v, const size_type u) {
		assert(v < size());
		assert(u < size());
		assert(connected(v, u));
		reroot(get_ptr(v));
		expose(get_ptr(u));
		return nodes[u].sum;
	}

	void link(const size_type parent, const size_type child) {
		assert(parent < size());
		assert(child < size());
		assert(!connected(parent, child));
		reroot(get_ptr(child));
		nodes[child].parent = get_ptr(parent);
	}
	void cut(const size_type v) {
		assert(v < size());
		expose(get_ptr(v));
		nodes[v].left->parent = nullptr;
		nodes[v].left = nullptr;
		nodes[v].sum = nodes[v].value;
	}
	void update_path(const size_type v, const size_type u,
		const operator_type &value) {
		assert(v < size());
		assert(u < size());
		assert(connected(v, u));
		reroot(get_ptr(v));
		expose(get_ptr(u));
		nodes[u].lazy = value;
	}
	template <class F> void update_vertex(const size_type v, const F &f) {
		assert(v < size());
		expose(get_ptr(v));
		nodes[v].value = f(::std::move(nodes[v].value));
		calc(get_ptr(v));
	}
};

#include <cstddef>
#include <utility>
template <class T, class Size = ::std::size_t> class sum_monoid {
public:
	using size_type = Size;
	using value_type = ::std::pair<T, size_type>;
	static T get(const value_type &x) { return x.first; }
	static value_type operation(const value_type &x, const value_type &y) {
		return value_type(x.first + y.first, x.second + y.second);
	}
	static value_type identity() { return value_type(T(0), size_type(0)); }
	static value_type reverse(const value_type &x) { return x; }
};

template <class T> class plus_monoid {
public:
	using value_type = T;
	static value_type operation(const value_type &x, const value_type &y) {
		return x + y;
	}
	static value_type identity() { return value_type(0); }
	static value_type reverse(const value_type &x) { return x; }
};

template <class T, class Size = ::std::size_t> class sum_plus {
public:
	static ::std::pair<T, Size> operation(const ::std::pair<T, Size> &x,
		const T &y) {
		return ::std::pair<T, Size>(x.first + y * x.second, x.second);
	}
};

#include<cstdio>
using u32 = unsigned int;

void scan(u32 &d) {
	d = 0;
	int c;
	while (c = fgetc(stdin), c == '\n' || c == ' ');
	do
		d = d * 10 + c - '0';
	while (c = fgetc(stdin), c != '\n' && c != ' ');
}

int main() {
	using u64 = unsigned long long;
	using tp = sum_monoid<u64>::value_type;

	u32 n;
	scan(n);

	::std::vector<tp> a(n, { 1,1 });

	lazy_st_trees<sum_monoid<u64>,
		plus_monoid<u64>,
		sum_plus<u64>> st(a.begin(),a.end());

	
	for (int i = 0;i < n;++i)
		st.update_vertex(i, [](tp) {return tp(1, 1);});

	u32 u, v;
	while (--n) {
		scan(u);
		scan(v);
		st.link(u - 1, v - 1);
	}

	scan(n);

	u64 ans = 0;

	while (n--) {
		scan(u);
		scan(v);
		ans += st.fold_path(u - 1, v - 1).first;
		st.update_path(u - 1, v - 1, 1);
	}

	printf("%llu\n", ans);

	return 0;
}

yukicoder

結果

テストケース

ソースコード