#876327 (C++17(clang)) No.772 Dynamic Distance Sum

提出ソース

結果

問題	No.772 Dynamic Distance Sum
ユーザー	Jaehyun Koo
提出日時	2023-05-31 23:41:43
言語	C++17(clang) (17.0.6 + boost 1.83.0)
結果	AC
実行時間	1,120 ms / 5,000 ms
コード長	13,722 bytes
コンパイル時間	3,668 ms
コンパイル使用メモリ	165,888 KB
実行使用メモリ	34,688 KB
最終ジャッジ日時	2024-06-08 21:15:48
合計ジャッジ時間	24,333 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	6 ms 5,376 KB
testcase_05	AC	3 ms 5,376 KB
testcase_06	AC	5 ms 5,376 KB
testcase_07	AC	3 ms 5,376 KB
testcase_08	AC	4 ms 5,376 KB
testcase_09	AC	6 ms 5,376 KB
testcase_10	AC	5 ms 5,376 KB
testcase_11	AC	3 ms 5,376 KB
testcase_12	AC	1,120 ms 29,952 KB
testcase_13	AC	1,065 ms 29,824 KB
testcase_14	AC	871 ms 29,824 KB
testcase_15	AC	806 ms 30,336 KB
testcase_16	AC	866 ms 29,952 KB
testcase_17	AC	1,045 ms 29,952 KB
testcase_18	AC	673 ms 29,824 KB
testcase_19	AC	1,067 ms 29,824 KB
testcase_20	AC	612 ms 30,080 KB
testcase_21	AC	1,080 ms 34,048 KB
testcase_22	AC	1,023 ms 33,920 KB
testcase_23	AC	853 ms 33,920 KB
testcase_24	AC	799 ms 34,688 KB
testcase_25	AC	861 ms 34,048 KB
testcase_26	AC	1,022 ms 33,920 KB
testcase_27	AC	849 ms 33,920 KB
testcase_28	AC	1,038 ms 33,920 KB
testcase_29	AC	683 ms 34,688 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
// Source: https://github.com/ecnerwala/cp-book/blob/master/src/top_tree.hpp

/**
 * Top tree!
 *
 * Usage:
 *   Make a `struct T : public top_tree_node_base<T>` (CRTP), which implements
 *     void update()
 *     void downdate()
 *     void do_flip_path()
 *     void do_other_operation() ...
 *   When update() is called, you can assume downdate() has already been called.
 *
 *   In general, do_op() should eagerly apply the operation but not touch the
 *   children. In downdate(), you can push down to the children with ch->do_op().
 *   WARNING: if different operations do not trivially commute, you *must*
 *   implement a way to swap/alter them to compose in a consistent order, and you
 *   must use that order when implementing downdate(). This can be nontrivial!
 *
 *   Creating vertices:
 *     n->is_path = n->is_vert = true;
 *     n->update();
 *
 *   Creating edges: no setup/update() needed, just call
 *     link(e, va, vb);
 *
 *   Updates:
 *     auto cur = get_path(va, vb); // or get_subtree(va, vb)
 *     cur->do_stuff();
 *     cur->downdate();
 *     cur->update_all();
 *
 * Node types:
 *   path edges: compress(c[0], self, c[1])
 *     assert(is_path && !is_vert);
 *     assert(c[0] && c[1]);
 *     assert(c[0]->is_path && c[1]->is_path);
 *     assert(!c[2]);
 *   (path) vertices: self + rake(c[0], c[1])
 *     assert(is_path && is_vert);
 *     assert(!c[2]);
 *     if (c[0]) assert(!c[0]->is_path);
 *     if (c[1]) assert(!c[1]->is_path);
 *   non-path edges: rake(c[0], self + c[2], c[1])
 *     assert(!is_path && !is_vert);
 *     assert(c[2])
 *     assert(c[2]->is_path);
 *     if (c[0]) assert(!c[0]->is_path);
 *     if (c[1]) assert(!c[1]->is_path);
 */

template <typename top_tree_node> struct top_tree_node_base {
  private:
	top_tree_node *derived_this() { return static_cast<top_tree_node *>(this); }
	const top_tree_node *derived_this() const { return static_cast<const top_tree_node *>(this); }

  public:
	mutable top_tree_node *p = nullptr;
	std::array<top_tree_node *, 3> c{nullptr, nullptr, nullptr};

	int d() const {
		assert(p);
		if (this == p->c[0]) {
			return 0;
		} else if (this == p->c[1]) {
			return 1;
		} else if (this == p->c[2]) {
			return 2;
		} else
			assert(false);
	}
	top_tree_node *&p_c() const { return p->c[d()]; } // p->c which points to you

	// 3 types of verts: path edges, path verts, non-path edges
	bool is_path;
	bool is_vert;

	bool r() const { return !p || p->is_path != is_path; }

  private:
	// Convenience wrappers for the derived functions.
	void do_flip_path() { derived_this()->do_flip_path(); }
	void downdate() { derived_this()->downdate(); }
	void update() { derived_this()->update(); }

  public:
	void downdate_all() {
		if (p)
			p->downdate_all();
		downdate();
	}

	// Returns the root
	top_tree_node *update_all() {
		top_tree_node *cur = derived_this();
		cur->update();
		while (cur->p) {
			cur = cur->p;
			cur->update();
		}
		return cur;
	}

  private:
	void rot() {
		assert(!is_vert);
		assert(!r());
		top_tree_node *pa = p;
		int x = d();
		assert(x == 0 || x == 1);
		top_tree_node *ch = c[!x];

		if (pa->p)
			pa->p_c() = derived_this();
		this->p = pa->p;

		pa->c[x] = ch;
		if (ch)
			ch->p = pa;

		this->c[!x] = pa;
		pa->p = derived_this();

		pa->update();
	}

	void rot_2(int c_d) {
		assert(!is_vert);
		assert(!r());
		assert(c[c_d]);
		assert(!c[c_d]->is_vert);

		if (d() == c_d) {
			rot();
			return;
		}

		top_tree_node *pa = p;
		int x = d();
		assert(x == 0 || x == 1);
		assert(c_d == !x);
		top_tree_node *ch = c[c_d]->c[!x];

		if (pa->p)
			pa->p_c() = derived_this();
		this->p = pa->p;

		pa->c[x] = ch;
		if (ch)
			ch->p = pa;

		this->c[c_d]->c[!x] = pa;
		pa->p = this->c[c_d];

		pa->update();
	}

	void splay_dir(int x) {
		while (!r() && d() == x) {
			if (!p->r() && p->d() == x) {
				p->rot();
			}
			rot();
		}
	}

	void splay_2(int c_d) {
		assert(!is_vert && is_path);
		assert(c[c_d] && !c[c_d]->is_vert);
		while (!r()) {
			if (!p->r()) {
				if (p->d() == d()) {
					p->rot();
				} else {
					rot_2(c_d);
				}
			}
			rot_2(c_d);
		}
	}

	void splay_2() {
		assert(!is_vert && is_path);
		assert(!r());
		p->splay_2(d());
	}

	void splay_vert() {
		assert(is_vert);
		if (r()) {
			return;
		}
		p->splay_dir(d());
		if (p->r()) {
			return;
		}

		assert(p->d() != d());
		// we have a preference to be the left child
		if (d() == 1) {
			p->rot();
		}
		assert(d() == 0);

		p->splay_2();
		assert(d() == 0);
		assert(p->d() == 1);
		assert(p->p->r());
	}

	void splay() {
		assert(!is_vert);
		while (!r()) {
			if (!p->r()) {
				if (p->d() == d()) {
					p->rot();
				} else {
					rot();
				}
			}
			rot();
		}
	}

	top_tree_node *cut_right() {
		assert(is_vert && is_path);
		splay_vert();

		if (r() || d() == 1) {
			assert(r() || (d() == 1 && p->r()));
			assert(c[0] == nullptr);
			return nullptr;
		}

		top_tree_node *pa = p;
		assert(pa->r() || (pa->d() == 1 && pa->p->r()));
		assert(!pa->is_vert);
		assert(pa->is_path);
		assert(pa->c[0] == this);
		assert(pa->c[2] == nullptr);

		if (pa->p)
			pa->p_c() = derived_this();
		this->p = pa->p;

		pa->is_path = false;
		pa->c[2] = pa->c[1]; // don't need to change the parent

		pa->c[0] = c[0];
		if (c[0])
			c[0]->p = pa;
		pa->c[1] = c[1];
		if (c[1])
			c[1]->p = pa;

		c[0] = nullptr;
		c[1] = pa;
		pa->p = derived_this();
		assert(c[2] == nullptr);

		assert(c[0] == nullptr);

		pa->update();
		return pa;
	}

	top_tree_node *splice_non_path() {
		assert(!is_path);
		assert(!is_vert);

		splay();
		assert(p && p->is_vert && p->is_path);
		p->cut_right();

		if (!p->is_path)
			rot();
		assert(p && p->is_vert && p->is_path);
		assert(p->r() || (p->d() == 1 && p->p->r()));
		assert(p->c[d()] == this && p->c[!d()] == nullptr);

		top_tree_node *pa = p;

		if (pa->p)
			pa->p_c() = derived_this();
		this->p = pa->p;

		pa->c[0] = c[0];
		if (c[0])
			c[0]->p = pa;
		pa->c[1] = c[1];
		if (c[1])
			c[1]->p = pa;

		assert(c[2] && c[2]->is_path);
		c[1] = c[2]; // don't need to change parent
		c[0] = pa;
		pa->p = derived_this();
		c[2] = nullptr;

		is_path = true;

		pa->update();
		return pa;
	}

	// Return the topmost vertex which was spliced into
	top_tree_node *splice_all() {
		top_tree_node *res = nullptr;
		for (top_tree_node *cur = derived_this(); cur; cur = cur->p) {
			if (!cur->is_path) {
				res = cur->splice_non_path();
			}
			assert(cur->is_path);
		}
		return res;
	}

  public:
	// Return the topmost vertex which was spliced into
	top_tree_node *expose() {
		assert(is_vert);
		downdate_all();

		top_tree_node *res = splice_all();

		cut_right();

		update_all();

		return res;
	}

	// Return the topmost vertex which was spliced into
	top_tree_node *expose_edge() {
		assert(!is_vert);
		downdate_all();

		top_tree_node *v = is_path ? c[1] : c[2];
		v->downdate();

		while (!v->is_vert) {
			v = v->c[0];
			v->downdate();
		}

		top_tree_node *res = v->splice_all();
		v->cut_right();
		v->update_all();

		assert(!p);
		assert(v == c[1]);

		return res;
	}

	// Return the new root
	top_tree_node *meld_path_end() {
		assert(!p);
		top_tree_node *rt = derived_this();
		while (true) {
			rt->downdate();
			if (rt->is_vert)
				break;
			rt = rt->c[1];
		}
		assert(rt->is_vert);
		rt->splay_vert();
		if (rt->c[0] && rt->c[1]) {
			top_tree_node *ch = rt->c[1];
			while (true) {
				ch->downdate();
				if (!ch->c[0])
					break;
				ch = ch->c[0];
			}
			ch->splay();
			assert(ch->c[0] == nullptr);

			ch->c[0] = rt->c[0];
			ch->c[0]->p = ch;

			rt->c[0] = nullptr;

			ch->update();
		} else if (rt->c[0]) {
			rt->c[1] = rt->c[0];
			rt->c[0] = nullptr;
		}
		assert(rt->c[0] == nullptr);
		return rt->update_all();
	}

	void make_root() {
		expose();

		top_tree_node *rt = derived_this();
		while (rt->p) {
			assert(rt->d() == 1);
			rt = rt->p;
		}
		rt->do_flip_path();
		rt->meld_path_end();

		expose();

		assert(!p);
	}

	// Link v2 as a child of v1 with edge e
	friend void link(top_tree_node *e, top_tree_node *v1, top_tree_node *v2) {
		assert(e && v1 && v2);
		assert(!e->c[0] && !e->c[1] && !e->c[2]);
		v1->expose();
		while (v1->p)
			v1 = v1->p;
		v2->make_root();

		assert(!v1->p);
		assert(!v2->p);

		e->is_path = true, e->is_vert = false;
		e->c[0] = v1;
		v1->p = e;
		e->c[1] = v2;
		v2->p = e;
		e->update();
	}

	// Link v2's root as a child of v1 with edge e
	// Returns false if they're already in the same subtree
	friend bool link_root(top_tree_node *e, top_tree_node *v1, top_tree_node *v2) {
		assert(e && v1 && v2);
		assert(!e->c[0] && !e->c[1] && !e->c[2]);
		v1->expose();
		v2->expose();

		while (v1->p)
			v1 = v1->p;
		while (v2->p)
			v2 = v2->p;
		if (v1 == v2)
			return false;

		assert(!v1->p);
		assert(!v2->p);

		e->is_path = true, e->is_vert = false;
		e->c[0] = v1;
		v1->p = e;
		e->c[1] = v2;
		v2->p = e;
		e->update();

		return true;
	}

	// Cuts the edge e
	// Returns the top-tree-root of the two halves; they are not necessarily the split vertices.
	friend std::pair<top_tree_node *, top_tree_node *> cut(top_tree_node *e) {
		assert(!e->is_vert);
		e->expose_edge();

		assert(!e->p);
		assert(e->is_path);

		top_tree_node *l = e->c[0];
		top_tree_node *r = e->c[1];
		assert(l && r);

		e->c[0] = e->c[1] = nullptr;
		l->p = r->p = nullptr;

		assert(e->c[2] == nullptr);

		l = l->meld_path_end();

		return {l, r};
	}

	friend top_tree_node *get_path(top_tree_node *a, top_tree_node *b) {
		assert(a->is_vert && b->is_vert);
		a->make_root();
		b->expose();
		if (a == b) {
			assert(!b->p);
			return b;
		}
		assert(!b->p->p);
		return b->p;
	}

	friend top_tree_node *get_subtree(top_tree_node *rt, top_tree_node *n) {
		rt->make_root();
		n->expose();
		return n;
	}
	friend top_tree_node *find_centroid(top_tree_node *p) {
		int N = p->sub;
		if (N == 0) {
			p->make_root();

			return p;
		}
		while (p->maxsub * 2 > N) {
			assert(p->is_vert);
			while (true) {
				p->downdate();
				if (p->c[0] && p->c[0]->maxsub * 2 > N) {
					p = p->c[0];
				} else if (p->c[1] && p->c[1]->maxsub * 2 > N) {
					p = p->c[1];
				} else {
					assert(p->c[2]);
					assert(p->c[2]->sub * 2 > N);
					p = p->c[2];
					break;
				}
			}
			assert(p->is_path);
			// now in path tree
			// go leftward as much as possible, while right sum <= N / 2
			int rightSum = 0;
			while (!p->is_vert) {
				p->downdate();
				if (rightSum + p->c[1]->sub <= N / 2) {
					rightSum += p->c[1]->sub;
					p = p->c[0];
				} else
					p = p->c[1];
			}
			// again, we are at the vertex
		}
		p->make_root();
		return p;
	}
};

struct node : public top_tree_node_base<node> {
	bool lazy_flip_path = false;

	// subtree sums
	int mine = 1;
	int sub = 0;
	int maxsub = 0;

	// basic properties
	int idx = 0;
	int weight = 0;

	// paths
	lint sum_edges = 0;
	lint sum_contribs[2] = {};

	void do_flip_path() {
		assert(is_path);
		std::swap(c[0], c[1]);
		swap(sum_contribs[0], sum_contribs[1]);
		lazy_flip_path ^= 1;
	}

	void downdate() {
		if (lazy_flip_path) {
			assert(is_path);
			if (!is_vert) {
				c[0]->do_flip_path();
				c[1]->do_flip_path();
			}
			lazy_flip_path = false;
		}
	}

	// NOTE: You may assume downdate() has been called on the current node, but
	// it may not have been called on the children! In particular, be careful
	// when accessing grandchildren information.
	void update() {
		sub = (is_vert && mine);
		maxsub = 0;
		sum_edges = 0;
		sum_contribs[0] = sum_contribs[1] = 0;
		if (is_path) {
			if (is_vert) {
				for (int i = 0; i < 3; i++) {
					if (c[i]) {
						sum_contribs[0] += c[i]->sum_contribs[0];
						sum_contribs[1] += c[i]->sum_contribs[0];
					}
				}
			} else {
				sum_edges = c[0]->sum_edges + c[1]->sum_edges + weight;
				sum_contribs[0] = c[0]->sum_contribs[0] + c[1]->sum_contribs[0] + c[1]->sub * (weight + c[0]->sum_edges);
				sum_contribs[1] = c[0]->sum_contribs[1] + c[1]->sum_contribs[1] + c[0]->sub * (weight + c[1]->sum_edges);
			}
		} else {
			for (int i = 0; i < 3; i++) {
				if (c[i]) {
					sum_contribs[0] += c[i]->sum_contribs[0];
					sum_contribs[1] += c[i]->sum_contribs[0];
					if (i == 2) {
						sum_contribs[0] += c[i]->sub * weight;
						sum_contribs[1] += c[i]->sub * weight;
					}
				}
			}
		}
		for (int i = 0; i < 3; i++) {
			if (c[i]) {
				sub += c[i]->sub;
				if (!is_path && i == 2)
					maxsub = max(maxsub, c[i]->sub);
				else
					maxsub = max(maxsub, c[i]->maxsub);
			}
		}
	}
};
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	vector<node *> ptr(n);
	for (int i = 0; i < n; i++) {
		ptr[i] = new node();
		ptr[i]->is_path = ptr[i]->is_vert = true;
		ptr[i]->idx = i;
		ptr[i]->mine = 1;
		ptr[i]->update();
	}
	lint S = 0;
	auto readVtx = [&]() {
		int x;
		cin >> x;
		return (x - 1 + S) % n;
	};
	map<pi, node *> mp;
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int a = readVtx();
			int b = readVtx();
			int c;
			cin >> c;
			if (a > b)
				swap(a, b);
			node *e = new node();
			e->weight = c;
			//	cout << "link " << a << " " << b << endl;

			link(e, ptr[a], ptr[b]);
			mp[pi{a, b}] = e;
		}
		if (t == 2) {
			int a = readVtx();
			int b = readVtx();
			//	cout << "cut " << a << " " << b << endl;
			if (a > b)
				swap(a, b);
			cut(mp[pi{a, b}]);
			mp.erase(mp.find(pi{a, b}));
		}
		if (t == 3) {
			int a = readVtx();
			ptr[a]->make_root();
			ptr[a]->mine ^= 1;
			ptr[a]->update();
			auto p = find_centroid(ptr[a]);
			cout << p->sum_contribs[0] << "\n";
			S += p->sum_contribs[0];
			S %= n;
		}
	}
}

yukicoder

結果

テストケース

ソースコード