oj.uz

Submission #120253

# Submission time Handle Problem Language Result Execution time Memory
120253 2019-06-24T05:49:19 Z JustInCase Synchronization (JOI13_synchronization) C++17
100 / 100
 275 ms 12272 KB 
#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

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.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 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 14 ms 1472 KB Output is correct
8 Correct 12 ms 1408 KB Output is correct
9 Correct 12 ms 1536 KB Output is correct
10 Correct 171 ms 11256 KB Output is correct
11 Correct 144 ms 11256 KB Output is correct
12 Correct 143 ms 11256 KB Output is correct
13 Correct 114 ms 10872 KB Output is correct
14 Correct 145 ms 10744 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 10900 KB Output is correct
2 Correct 111 ms 11000 KB Output is correct
3 Correct 77 ms 10744 KB Output is correct
4 Correct 75 ms 10616 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 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 3 ms 512 KB Output is correct
7 Correct 13 ms 1408 KB Output is correct
8 Correct 165 ms 12080 KB Output is correct
9 Correct 169 ms 12024 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 12152 KB Output is correct
2 Correct 118 ms 11896 KB Output is correct
3 Correct 114 ms 11788 KB Output is correct
4 Correct 109 ms 11868 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 3 ms 512 KB Output is correct
6 Correct 13 ms 1408 KB Output is correct
7 Correct 183 ms 12196 KB Output is correct
8 Correct 163 ms 12064 KB Output is correct
9 Correct 133 ms 12024 KB Output is correct
10 Correct 275 ms 12028 KB Output is correct
11 Correct 147 ms 12272 KB Output is correct
12 Correct 146 ms 12152 KB Output is correct
13 Correct 112 ms 11896 KB Output is correct