Submission #120465

#	Time	Username	Problem	Language	Result	Execution time	Memory
120465		perchem	동기화 (JOI13_synchronization)	C++14	100 / 100	234 ms	9848 KiB

synchronization

#include <iostream>
#include <cstdint>
#include <random>
#include <utility>
#include <cassert>

class Node {
private:
	static std::mt19937 rnd;

	Node *l, *r, *par;
	Node *pp;
	uint32_t p;
	bool lazy;
	uint32_t size;


	void push_lazy() {
		if (lazy) {
			if (l) {
				l->reverse();
			}
			if (r) {
				r->reverse();
			}
			lazy = false;
		}
	}
	void push_lazy_root() {
		if (par) {
			par->push_lazy_root();
		}
		push_lazy();
	}

	void recalc() {
		par = nullptr;
		size = 1;

		if (l) {
			size += l->size;
			l->par = this;
			if (l->pp) {
				pp = l->pp;
				l->pp = nullptr;
			}
		}
		if (r) {
			size += r->size;
			r->par = this;
			if (r->pp) {
				pp = r->pp;
				r->pp = nullptr;
			}
		}
	}

public:
	uint32_t inf; //0 for non root, actual value for root
	
	void reverse() {
		lazy = !lazy;
		std::swap(l, r);
	}

	Node(): l(nullptr), r(nullptr), par(nullptr), pp(nullptr), p(rnd()),
		lazy(false), size(1), inf(1) {}
	
	static Node* merge(Node *a, Node *b) {
		if (a == nullptr) {
			return b;
		} else if (b == nullptr) {
			return a;
		} else if (a->p > b->p) {
			a->push_lazy();
			a->r = merge(a->r, b);
			a->recalc();
			return a;
		} else {
			b->push_lazy();
			b->l = merge(a, b->l);
			b->recalc();
			return b;
		}
	}
	static std::pair<Node*, Node*> split(Node *a, uint32_t sz) {
		if (a == nullptr) {
			return {nullptr, nullptr};
		}
		a->push_lazy();
		uint32_t lSz = a->l ? a->l->size : 0;
		if (lSz >= sz) {
			auto s = split(a->l, sz);
			a->l = s.second;
			a->recalc();
			return {s.first, a};
		} else {
			auto s = split(a->r, sz - lSz - 1);
			a->r = s.first;
			a->recalc();
			return {a, s.second};
		}
	}
	Node *treap_root() {
		assert(par != this);
		return par ? par->treap_root() : this;
	}
	uint32_t ind() {
		push_lazy_root();
		uint32_t ans = l ? l->size : 0;

		Node *v = this;
		while (v->par) {
			if (v->par->r == v) {
				ans += v->par->l ? v->par->l->size : 0;
				ans++;
			}
			v = v->par;
		}
		return ans;
	}
	Node *left_most() {
		push_lazy();
		return l ? l->left_most() : this;
	}

	void split_at_node() {
		uint32_t i = ind();
		Node *root = treap_root();
		Node *rootPp = root->pp;
		root->pp = nullptr;

		//std::cerr << "i: " << i << "\n";

		auto s = split(root, i + 1);
		s.first->pp = rootPp;
		if (s.second) {
			s.second->pp = this;
		}
	}

	void access() {
		split_at_node();
		//std::cerr << "split_at_node();\n";
		Node *v = treap_root();
		while (v->pp) {
			Node *u = v->pp;
			u->split_at_node();
			v->pp = nullptr;
			//assert(u->treap_root() != v);
			v = merge(u->treap_root(), v);
		}
	}

	void reroot() {
		access();
		Node *treapRoot = treap_root();

		Node *treeRoot = treapRoot->left_most();
		uint32_t inf = treapRoot->left_most()->inf;
		treeRoot->inf = 0;
		
		treapRoot->reverse();
		treapRoot->left_most()->inf = inf;
	}

	static void link(Node *a, Node *b, uint32_t prevInf = 0) {
		a->access();
		Node *rootA = a->treap_root()->left_most();
		b->reroot();

		rootA->inf += b->inf - prevInf;
		b->inf = 0;

		b->treap_root()->pp = a;
	}
	uint32_t depth() {
		access();
		return treap_root()->size;
	}
	static uint32_t cut(Node *a, Node *b) {
		if (a->depth() < b->depth()) {
			std::swap(a, b);
		}
		a->inf = b->treap_root()->left_most()->inf;
		b->access();
		a->treap_root()->pp = nullptr;
		return a->inf;
	}
	void print_treap() {
	}

	uint32_t id();
};

std::mt19937 Node::rnd(27071999);

const uint32_t MAX_N = 1e5 + 10;
const uint32_t MAX_M = 2e5 + 10;

struct Edge {
	uint32_t a, b;
	uint32_t lastI;
	bool on;

	Edge(): lastI(0), on(false) {}
};

std::vector<Node> nodes;
std::vector<Edge> edges;
uint32_t m, q;

uint32_t Node::id() {
	return this - &nodes[0] + 1;
}

void print_info() {
	for (Node &n : nodes) {
		n.access();
		std::cerr << "(" << n.id() << ": " << n.treap_root()->left_most()->id();
		std::cerr << " " << n.treap_root()->left_most()->inf << ") ";
	}
	std::cerr << "\n";
}

void print_treaps() {
	for (uint32_t i = 0;i < nodes.size();i++) {
		std::cerr << i << ": " << nodes[i].treap_root() - &nodes[0] << "; ";
		std::cerr << "accessing it\n";
		nodes[i].access();
	}
	std::cerr << "\n";
}
void input() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	uint32_t n;
	std::cin >> n >> m >> q;
	nodes.resize(n);

	edges.resize(n - 1);
	for (Edge &e : edges) {
		std::cin >> e.a >> e.b;
		e.a--;
		e.b--;
	}
}

void do_updates() {
	//print_treaps();
	for (uint32_t i = 0;i < m;i++) {
		uint32_t j;
		std::cin >> j;
		Edge &e = edges[j - 1];
		if (e.on) {
			e.lastI = Node::cut(&nodes[e.a], &nodes[e.b]);
		} else {
			Node::link(&nodes[e.a], &nodes[e.b], e.lastI);
		}
		e.on = !e.on;
		//print_info();

		//print_treaps();
	}
}

void ans_queries() {
	for (uint32_t i = 0;i < q;i++) {
		uint32_t a;
		std::cin >> a;
		nodes[a - 1].access();
		std::cout << nodes[a - 1].treap_root()->left_most()->inf << "\n";
	}
}

int main() {
	input();
	do_updates();
	ans_queries();
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40