oj.uz

Submission #120465

# Submission time Handle Problem Language Result Execution time Memory
120465 2019-06-24T15:35:20 Z perchem Synchronization (JOI13_synchronization) C++14
100 / 100
 234 ms 9848 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 9 ms 1152 KB Output is correct
8 Correct 8 ms 1124 KB Output is correct
9 Correct 9 ms 1280 KB Output is correct
10 Correct 86 ms 8952 KB Output is correct
11 Correct 101 ms 8964 KB Output is correct
12 Correct 90 ms 8968 KB Output is correct
13 Correct 65 ms 8580 KB Output is correct
14 Correct 71 ms 8404 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 8696 KB Output is correct
2 Correct 92 ms 8648 KB Output is correct
3 Correct 61 ms 8440 KB Output is correct
4 Correct 62 ms 8344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 9 ms 1280 KB Output is correct
8 Correct 114 ms 9716 KB Output is correct
9 Correct 119 ms 9708 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 9748 KB Output is correct
2 Correct 112 ms 9464 KB Output is correct
3 Correct 113 ms 9572 KB Output is correct
4 Correct 116 ms 9568 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 10 ms 1312 KB Output is correct
7 Correct 127 ms 9756 KB Output is correct
8 Correct 109 ms 9796 KB Output is correct
9 Correct 92 ms 9720 KB Output is correct
10 Correct 234 ms 9716 KB Output is correct
11 Correct 140 ms 9752 KB Output is correct
12 Correct 139 ms 9848 KB Output is correct
13 Correct 116 ms 9592 KB Output is correct