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

提出ソース

結果

問題	No.399 動的な領主
ユーザー	noshi91
提出日時	2018-09-14 21:47:04
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	205 ms / 2,000 ms
コード長	7,041 bytes
コンパイル時間	621 ms
コンパイル使用メモリ	61,680 KB
実行使用メモリ	9,532 KB
最終ジャッジ日時	2023-09-20 13:43:50
合計ジャッジ時間	3,533 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	2 ms 4,376 KB
testcase_05	AC	13 ms 4,376 KB
testcase_06	AC	205 ms 9,472 KB
testcase_07	AC	197 ms 9,388 KB
testcase_08	AC	187 ms 9,472 KB
testcase_09	AC	185 ms 9,460 KB
testcase_10	AC	3 ms 4,380 KB
testcase_11	AC	9 ms 4,376 KB
testcase_12	AC	110 ms 9,448 KB
testcase_13	AC	104 ms 9,512 KB
testcase_14	AC	31 ms 9,532 KB
testcase_15	AC	90 ms 9,452 KB
testcase_16	AC	99 ms 9,452 KB
testcase_17	AC	185 ms 9,444 KB
testcase_18	AC	185 ms 9,452 KB

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

ソースコード

raw source code

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

template <class ValueMonoid, class OperatorMonoid, class Modifier>
class lazy_st_trees {
public:
	using value_structure = ValueMonoid;
	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
		node_type(node_type *const p)
			: left(p), right(p), parent(p), value(value_structure::identity()),
			sum(value_structure::identity()),
			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) {
		ptr->lazy = operator_structure::reverse(::std::move(ptr->lazy));
		ptr->reversed ^= 1;
	}
	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);
		}
		ptr->left->lazy = operator_structure::operation(ptr->left->lazy, ptr->lazy);
		ptr->right->lazy =
			operator_structure::operation(ptr->right->lazy, ptr->lazy);
		ptr->value = modifier::operation(ptr->value, ptr->lazy);
		ptr->lazy = operator_structure::identity();
	}
	static void propagate(pointer ptr) {
		pointer prev = nullptr;
		while (ptr != nil()) {
			::std::swap(ptr->parent, prev);
			::std::swap(ptr, prev);
		}
		while (prev) {
			push(prev);
			::std::swap(prev->parent, ptr);
			::std::swap(prev, ptr);
		}
		nil()->sum = value_structure::identity();
		nil()->lazy = operator_structure::identity();
		nil()->reversed = 0;
	}
	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) {
		ptr->sum = value_structure::operation(
			value_structure::operation(reflect(ptr->left), ptr->value),
			reflect(ptr->right));
	}
	static void rotate_l(const pointer ptr, const pointer ch) {
		ptr->right = 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;
		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->left == y) {
				y = x->parent;
				ptr->parent = y->parent;
				if (y->left == x)
					rotate_r(y, x), rotate_r(x, ptr);
				else if (y->right == x)
					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;
				ptr->parent = y->parent;
				if (y->right == x)
					rotate_l(y, x), rotate_l(x, ptr);
				else if (y->left == x)
					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 = nil();
		while (x != nil()) {
			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; }
	static pointer nil() {
		static node_type leaf(nullptr);
		return &leaf;
	}

public:
	lazy_st_trees() : nodes() {}
	explicit lazy_st_trees(const size_type size)
		: nodes(size, node_type(nil())) {}

	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 != nil() || 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 = nil();
		nodes[v].left = nil();
		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;

	u32 n;
	scan(n);

	lazy_st_trees<sum_monoid<u64>,
		plus_monoid<u64>,
		sum_plus<u64>> st(n);

	using tp = sum_monoid<u64>::value_type;
	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

結果

テストケース

ソースコード