Submission #120253

#	Time	Username	Problem	Language	Result	Execution time	Memory
120253		JustInCase	Synchronization (JOI13_synchronization)	C++17	100 / 100	275 ms	12272 KiB

synchronization

#include <bits/stdc++.h>

const int32_t MAX_N = 1e5;
std::mt19937 mt(69);

struct Edge {
	bool toggled;
	int32_t x, y, w;

	Edge() {}
	Edge(int32_t _x, int32_t _y) : x(_x), y(_y), w(0), toggled(false) {}
};

struct Node {
	bool rev;
	int32_t sz, prior, sum, id;
	Node *l, *r, *par, *pp;

	Node() {}
	Node(int32_t _id) : id(_id) {
		sz = 1;
		prior = mt();
		sum = 1;

		rev = false;

		l = nullptr;
		r = nullptr;
		par = nullptr;
		pp = nullptr;
	}

	static int32_t get_size(Node *x) {
		return (x ? x->sz : 0);
	}

	static void push_lazy(Node *x) {
		if(!x) {
			return;
		}

		if(x->rev) {
			std::swap(x->l, x->r);

			if(x->l) {
				x->l->rev ^= 1;
			}
			if(x->r) {
				x->r->rev ^= 1;
			}

			x->rev = false;
		}
	}

	static void pull_info(Node *x) {
		if(!x) {
			return;
		}

		x->sz = get_size(x->l) + get_size(x->r) + 1;
		
		x->par = nullptr;
		if(x->l) {
			x->l->par = x;
		}
		if(x->r) {
			x->r->par = x;
		}

		if(x->l && x->l->pp) {
			x->pp = x->l->pp;
			x->l->pp = nullptr;
		}
		if(x->r && x->r->pp) {
			x->pp = x->r->pp;
			x->r->pp = nullptr;
		}
	}

	static Node* merge(Node *x, Node *y) {
		push_lazy(x);
		push_lazy(y);

		if(!x) {
			return y;
		}
		if(!y) {
			return x;
		}

		if(x->prior > y->prior) {
			x->r = merge(x->r, y);
			pull_info(x);
			return x;
		}
		else {
			y->l = merge(x, y->l);
			pull_info(y);
			return y;
		}
	}

	static std::pair< Node*, Node* > split(Node *x, int32_t key, int32_t add = 0) {
		push_lazy(x);

		if(!x) {
			return { nullptr, nullptr };
		}

		int32_t currKey = add + get_size(x->l);
		if(currKey <= key) {
			auto aux = split(x->r, key, currKey + 1);
			x->r = aux.first;
			
			pull_info(x);
			
			return { x, aux.second };
		}
		else {
			auto aux = split(x->l, key, add);
			x->l = aux.second;
			
			pull_info(x);

			return { aux.first, x };
		}
	}

	static Node* split_after(Node *x) {
		int32_t pos = get_pos(x);
		Node *u = get_root(x);
		
		Node *pp = u->pp;
		u->pp = nullptr;

		auto aux = split(u, pos);
		
		if(aux.second) {
			aux.second->pp = x;
		}
		u = aux.first;
		u->pp = pp;

		return u;
	}

	static int32_t get_pos(Node *x) {
		int32_t pos = get_size(x->l);
		while(x->par) {
			if(x->rev) {
				pos = get_size(x) - pos - 1;
			}
			if(x->par->r == x) {
				pos += get_size(x->par->l) + 1;	
			}
			
			x = x->par;
		}

		if(x->rev) {
			pos = get_size(x) - pos - 1;
		}

		return pos;
	}

	static Node* get_root(Node *x) {
		while(x->par) {
			x = x->par;
		}

		return x;
	}
};

Node *nodes[MAX_N + 5];
Edge edges[MAX_N + 5];

Node* access(Node *x) {
	Node *u = Node::split_after(x);
	while(u->pp) {
		Node *v = u->pp;
		v = Node::split_after(v);
		u->pp = nullptr;
		u = Node::merge(v, u);
	}
	return u;
}

Node* get_tree_root(Node *x) {
	x = access(x);
	while(x->l) {
		x = x->l;
	}

	return x;
}

void change_root(Node *x) {
	int32_t treeSum = get_tree_root(x)->sum;

	Node *v = access(x);
	v->rev ^= 1;

	Node *u = get_tree_root(x);
	u->sum = treeSum;
}

void link(Node *x, Node *y) {
	change_root(x);
	x->pp = y;
}

void cut(Node *x, Node *y) {
	change_root(x);
	y = access(y);

	Node::split(y, 0);
}

void toggle_edge(int32_t x) {
	if(edges[x].toggled) {
		int32_t sum = get_tree_root(nodes[edges[x].x])->sum;
		cut(nodes[edges[x].x], nodes[edges[x].y]);
		
		edges[x].w = sum;
		Node *v = get_tree_root(nodes[edges[x].x]);
		Node *u = get_tree_root(nodes[edges[x].y]);

		v->sum = sum;
		u->sum = sum;
	}
	else {
		int32_t sumX = get_tree_root(nodes[edges[x].x])->sum;
		int32_t sumY = get_tree_root(nodes[edges[x].y])->sum;

		link(nodes[edges[x].x], nodes[edges[x].y]);

		Node *u = get_tree_root(nodes[edges[x].x]);
		u->sum = sumX + sumY - edges[x].w;
	}

	edges[x].toggled ^= 1;
}

int32_t answer_query(Node *x) {
	return get_tree_root(x)->sum;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int32_t n, m, q;
	std::cin >> n >> m >> q;
	
	for(int32_t i = 1; i <= n; i++) {
		nodes[i] = new Node(i);
	}

	for(int32_t i = 1; i <= n - 1; i++) {
		int32_t x, y;
		std::cin >> x >> y;

		edges[i] = Edge(x, y);
	}

	for(int32_t i = 0; i < m; i++) {
		int32_t x;
		std::cin >> x;
		
		toggle_edge(x);
	}

	for(int32_t i = 0; i < q; i++) {
		int32_t x;
		std::cin >> x;

		std::cout << answer_query(nodes[x]) << '\n';
	}
}

Compilation message (stderr)

synchronization.cpp: In constructor 'Edge::Edge(int32_t, int32_t)':
synchronization.cpp:8:16: warning: 'Edge::w' will be initialized after [-Wreorder]
  int32_t x, y, w;
                ^
synchronization.cpp:7:7: warning:   'bool Edge::toggled' [-Wreorder]
  bool toggled;
       ^~~~~~~
synchronization.cpp:11:2: warning:   when initialized here [-Wreorder]
  Edge(int32_t _x, int32_t _y) : x(_x), y(_y), w(0), toggled(false) {}
  ^~~~

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