結果

問題 No.772 Dynamic Distance Sum
ユーザー kriiikriii
提出日時 2018-12-21 14:08:32
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,805 ms / 5,000 ms
コード長 6,166 bytes
コンパイル時間 952 ms
コンパイル使用メモリ 79,616 KB
実行使用メモリ 52,352 KB
最終ジャッジ日時 2024-09-25 09:26:12
合計ジャッジ時間 26,969 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 9 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 6 ms
5,376 KB
testcase_07 AC 4 ms
5,376 KB
testcase_08 AC 5 ms
5,376 KB
testcase_09 AC 10 ms
5,376 KB
testcase_10 AC 7 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 1,553 ms
36,096 KB
testcase_13 AC 1,410 ms
34,304 KB
testcase_14 AC 1,478 ms
40,448 KB
testcase_15 AC 1,115 ms
34,048 KB
testcase_16 AC 1,311 ms
36,736 KB
testcase_17 AC 1,449 ms
36,352 KB
testcase_18 AC 971 ms
39,808 KB
testcase_19 AC 1,380 ms
34,304 KB
testcase_20 AC 792 ms
40,448 KB
testcase_21 AC 1,422 ms
46,848 KB
testcase_22 AC 1,273 ms
44,544 KB
testcase_23 AC 1,805 ms
52,352 KB
testcase_24 AC 1,105 ms
44,416 KB
testcase_25 AC 1,251 ms
47,616 KB
testcase_26 AC 1,357 ms
47,232 KB
testcase_27 AC 1,223 ms
48,512 KB
testcase_28 AC 1,339 ms
44,928 KB
testcase_29 AC 883 ms
52,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

struct Node{
	Node(int weight_ = 1, int len_ = 0)
	{
		left = right = parent = nullptr;
		weight[0] = weight_; weight[1] = len_;
		size[0] = weight[0]; size[1] = weight[1]; hSize = 0;
		sum[0] = sum[1] = hSum = 0;
		reverse = false;
	}
	~Node()
	{
		makeRoot();
		if (right) right->parent = nullptr;
		for (auto &p : hNode) p.second->parent = nullptr;
	}
	Node *left, *right, *parent;
	long long weight[2], size[2], hSize, sum[2], hSum;
	bool reverse;
	set<pair<int, Node*> > hNode; // loser.

	bool isRoot();
	Node* successor();
	void propagate();
	void update();
	void rotate();
	void splay();
	Node* access();
	Node* lca(Node *node);
	void hidePath();
	void chainPath(Node *node);
	void makeRoot();
	void link(Node *node);
	void cut();

	void changeWeight(int weight);
	Node* findCenter();
};

struct LinkCutTree
{
	LinkCutTree(){}
	LinkCutTree(int size)
	{
		nodeList.resize(size);
		for (int i=0;i<size;i++) nodeList[i] = new Node;
	}
	vector<Node*> nodeList;

	void addNode(int weight = 1, int len = 0)
	{
		nodeList.emplace_back(new Node(weight, len));
	}

	Node* getNode(int i)
	{
		if (0 <= i && i < nodeList.size()) return nodeList[i];
		return nullptr;
	}
};

bool Node::isRoot()
{
	return this == nullptr || parent == nullptr || (parent->left != this && parent->right != this);
}

Node* Node::successor()
{
	propagate();
	Node* ret = right;
	if (ret){
		ret->propagate();
		while (ret->left){
			ret = ret->left;
			ret->propagate();
		}
	}
	return ret;
}

void Node::propagate()
{
	if (reverse){
		swap(left, right);
		swap(sum[0],sum[1]);
		if (left) left->reverse = !left->reverse;
		if (right) right->reverse = !right->reverse;
		reverse = false;
	}
}

void Node::update()
{
	size[0] = weight[0] + hSize;
	size[1] = weight[1];
	sum[0] = sum[1] = hSum;
	long long psum[2] = {size[0],size[0]}, qsum[2] = {size[1],size[1]};

	if (left){
		size[0] += left->size[0];
		size[1] += left->size[1];
		psum[1] += left->size[0];
		qsum[0] += left->size[1];
	}

	if (right){
		size[0] += right->size[0];
		size[1] += right->size[1];
		psum[0] += right->size[0];
		qsum[1] += right->size[1];
	}

	for (int k=0;k<2;k++){
		if (left) sum[k] += left->sum[k^left->reverse];
		if (right) sum[k] += right->sum[k^right->reverse];
		sum[k] += psum[k] * qsum[k];
	}
}

void Node::rotate()
{
	if (isRoot())
		return;

	Node *up = parent;
	up->propagate();
	propagate();

	Node *jump = up->parent;
	up->parent = this;

	Node *down = nullptr;
	if (up->left == this){
		up->left = down = right;
		right = up;
	}
	else{
		up->right = down = left;
		left = up;
	}
	if (down) down->parent = up;

	parent = jump;
	if (jump){
		int sz = up->size[0];
		auto I = jump->hNode.find({sz, up});
		if (I != jump->hNode.end()){
			jump->hNode.erase(I);
			jump->hNode.insert({sz, this});
		}
		else if (jump->left == up)
			jump->left = this;
		else if (jump->right == up)
			jump->right = this;
	}

	up->update();
	update();
}

void Node::splay()
{
	propagate();
	while (!isRoot()){
		Node *up = parent;
		if (!up->isRoot()){
			Node *jump = up->parent;
			if ((this == up->left) ^ (up == jump->left))
				rotate();
			else
				up->rotate();
		}
		rotate();
	}
}

Node* Node::access()
{
	hidePath();

	Node* last = this;
	while (parent){
		last = parent;
		parent->chainPath(this);
		splay();
	}

	return last;
}

Node* Node::lca(Node *node)
{
	access();
	Node *ret = node->access();
	if (ret == access()) return ret;
	return nullptr;
}

void Node::hidePath()
{
	splay();

	if (right && right->parent == this){
		hSize += right->size[0];
		hSum += right->sum[right->reverse];
		hNode.insert({right->size[0], right});
		right = nullptr;
		update();
	}
}

void Node::chainPath(Node *node)
{
	hidePath();

	if (node && node->parent == this && left != node){
		right = node;
		hSize -= right->size[0];
		hSum -= right->sum[right->reverse];
		hNode.erase({right->size[0], right});
		update();
	}
}

void Node::makeRoot()
{
	access();
	reverse = !reverse;
	propagate();
}

void Node::link(Node *node)
{
	if (!node)
		return;

	makeRoot();
	access();
	node->access();
	left = node;
	node->parent = this;
	update();
}

void Node::cut()
{
	if (!parent) return;

	access();
	if (left){
		left->parent = nullptr;
		left = nullptr;
	}
	splay();
}

void Node::changeWeight(int weight_)
{
	makeRoot();
	weight[0] = weight_;
	update();
}

Node* Node::findCenter()
{
	makeRoot();
	int full = size[0];
	if (full == 0) return this;
	int half = full / 2;

	Node *n = this;
	long long rem = 0;
	while (true){
		n->propagate();
		if (n->left){
			if (full - rem - n->size[0] + n->left->size[0] > half){
				rem += n->size[0] - n->left->size[0];
				n = n->left;
				continue;
			}
		}
		if (n->right){
			if (n->right->size[0] + rem > half){
				n = n->right;
				continue;
			}
		}
		if (!n->hNode.empty()){
			auto I = n->hNode.end(); --I;
			if (I->first > half){
				auto mv = I->second;
				n->splay();
				n = mv;
				rem = 0;
				continue;
			}
		}
		break;
	}

	n->makeRoot();
	if (n->weight[1]){
		n = n->successor();
		if (!n && !n->hNode.empty()) n = n->hNode.begin()->second;
		n->makeRoot();
	}
	return n;
}

int main()
{
	int N,Q; scanf ("%d %d",&N,&Q);

	LinkCutTree lct(N);
	map<pair<int, int>, Node *> edge;
	int enc = 0;
	while (Q--){
		int o; scanf ("%d",&o);

		if (o == 1){
			int x,y,c; scanf ("%d %d %d",&x,&y,&c);
			x = (x - 1 + enc) % N;
			y = (y - 1 + enc) % N;
			if (x > y) swap(x,y);
			Node *e = new Node(0,c);
			Node *p = lct.getNode(x);
			Node *q = lct.getNode(y);
			if (p->lca(q)) return 1;
			p->link(e);
			q->link(e);
			edge[{x,y}] = e;
		}
		else if (o == 2){
			int x,y; scanf ("%d %d",&x,&y);
			x = (x - 1 + enc) % N;
			y = (y - 1 + enc) % N;
			if (x > y) swap(x,y);
			auto I = edge.find({x,y});
			if (I != edge.end()){
				delete I->second;
				edge.erase(I);
			}
		}
		else if (o == 3){
			int x; scanf ("%d",&x);
			x = (x - 1 + enc) % N;
			auto v = lct.getNode(x);
			v->changeWeight(1 - v->weight[0]);
			auto c = v->findCenter();
			long long res = c->sum[c->reverse];
			enc = (enc + res) % N;
			printf ("%lld\n",res);
		}
	}

	return 0;
}
0