Heavy Light White Falcon – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Cerinta completa

Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem.

You are given a tree with nodes and each node’s value is initially . The problem asks you to operate the following two types of queries:

“1 u x” assign to the value of the node .
“2 u v” print the maximum value of the nodes on the unique path between and .

Input Format

First line consists of two integers seperated by a space: and .
Following lines consisting of two integers denotes the undirectional edges of the tree.
Following lines consist of the queries you are asked to operate.

Constraints

It is guaranteed that input denotes a connected tree with nodes. Nodes are enumerated with 0-based indexing.

Output Format

For each second type of query print single integer in a single line, denoting the asked maximum value.

Sample Input

Sample Output

Explanation

After the first two updates value of the th node is and st node is . That is why maxiumum value on the path between and is .

Limbajul de programare folosit: cpp14

Cod:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <inttypes.h>

typedef struct link {
	struct node1 *with;
	struct link *next;
} link;

typedef struct node1 {
	int id;
	int mark;
	int num_connections;
	link *connections;
} node1;

typedef struct segment {
	struct segment *parent, *left, *right;
	int height; //sideways and grows towards the root
	int low_depth, high_depth; //low is numerically *greater*, low==high when leaf
	int max_val;
} segment;

typedef struct node {
	struct node *parent;
	struct node *chain_head;
	int sub_size; //includes self

	int num_children;
	struct node **children;

	segment seg; //contains val and depth
} node;

node **out_storage = NULL;
node ***child_storage = NULL;
node **mapping = NULL;
node * directify(node1 *at, node *out_parent, int depth) {
	//assert(!at->mark);
	at->mark = 1;

	node *out = *out_storage;
	(*out_storage)++;

	out->seg.max_val = 0;
	out->seg.low_depth = depth;
	out->seg.high_depth = depth;
	out->seg.height = 0;
	out->seg.left = out->seg.right = out->seg.parent = NULL;

	out->parent = out_parent;
	out->num_children = at->num_connections - 1;
	out->children = (out->num_children == 0) ? NULL : *child_storage;
	out->sub_size = 1;
	(*child_storage) += out->num_children;

	mapping[at->id] = out;

	int ci = 0;
	for (link *l = at->connections; l; l = l->next) {
		node1 *to = l->with;
		if (!to->mark) {
			node *child = directify(to, out, depth + 1);
			out->children[ci++] = child;
			out->sub_size += child->sub_size;
		}
	}
	assert(ci == out->num_children);

	return out;
}

typedef struct segment_block {
	struct segment_block *prev;
	int use;
	segment segs[1024];
} segment_block;

int max(int a, int b) {
	return (a > b) ? a : b;
}

segment_block *front_block = NULL;
segment * new_segment(segment *left_child, segment *right_child) {
	if (!front_block || front_block->use == 1024) {
		segment_block *last = front_block;
		front_block = (segment_block*)calloc(1, sizeof(segment_block));
		front_block->prev = last;
		front_block->use = 0;
	}
	segment *seg = &front_block->segs[front_block->use++];
	//assert(left_child && right_child);
	//assert(left_child->low_depth >= left_child->high_depth);
	//assert(right_child->low_depth >= right_child->high_depth);
	//assert(left_child->high_depth > right_child->low_depth);

	seg->low_depth = left_child->low_depth;
	seg->high_depth = right_child->high_depth;
	seg->height = max(left_child->height, right_child->height) + 1;
	seg->left = left_child;
	seg->right = right_child;
	seg->max_val = max(left_child->max_val, right_child->max_val);
	seg->parent = NULL;
	left_child->parent = seg;
	right_child->parent = seg;

	return seg;
}

void build_chain_tree(node *final, node *chain_head, int chain_length) {
	static segment **stack = NULL;
	static int stack_length = 0;

	if (stack_length < chain_length) {
		stack_length = chain_length;
		stack = (segment**)realloc(stack, stack_length * sizeof(segment*));
	}

	node *at = final;
	int stack_size = 0;
	while (at && at->chain_head == chain_head) {
		stack[stack_size] = &at->seg;
		stack_size++;
		at = at->parent;

		while (stack_size > 1) {
			segment *r = stack[stack_size - 1];
			segment *l = stack[stack_size - 2];
			if (r->height == l->height) {
				segment *p = new_segment(l, r);
				stack[stack_size - 2] = p;
				stack_size--;
			}
			else {
				break;
			}
		}
	}

	//assert(stack_size >= 1);
	while (stack_size > 1) {
		segment *r = stack[stack_size - 1];
		segment *l = stack[stack_size - 2];
		//assert(r->height <= l->height);
		segment *p = new_segment(l, r);
		stack[stack_size - 2] = p;
		stack_size--;
	}
}

void hld(node *at, node *chain_head, int chain_length, int *num_chains) {
	if (!chain_head) {
		chain_head = at;
		(*num_chains)++;
	}

	at->chain_head = chain_head;

	node *most = NULL;
	for (int ci = 0; ci < at->num_children; ci++) {
		if (!most || most->sub_size < at->children[ci]->sub_size) {
			most = at->children[ci];
		}
	}

	for (int ci = 0; ci < at->num_children; ci++) {
		node *ch = at->children[ci];
		if (ch == most) {
			//continue chain
			hld(ch, chain_head, chain_length + 1, num_chains);
		}
		else {
			//start new chain
			hld(ch, NULL, 1, num_chains);
		}

	}

	if (!most) {
		//end of chain, build tree
		build_chain_tree(at, chain_head, chain_length);
	}
}

node * lca(node *u, node *v) {
	while (u->chain_head != v->chain_head) {
		if (u->chain_head->seg.low_depth < v->chain_head->seg.low_depth)
			v = v->chain_head->parent;
		else
			u = u->chain_head->parent;
	}
	return (u->seg.low_depth < v->seg.low_depth) ? u : v;
}

int segment_range_query(segment *at, int low_depth, int high_depth) {
	//assert(low_depth >= high_depth);
	//assert(at->low_depth >= low_depth);
	//assert(at->high_depth <= high_depth);

	if (at->low_depth == low_depth && at->high_depth == high_depth) {
		return at->max_val;
	}
	else {
		if (high_depth >= at->left->high_depth) {
			return segment_range_query(at->left, low_depth, high_depth);
		}
		else if (low_depth <= at->right->low_depth) {
			return segment_range_query(at->right, low_depth, high_depth);
		}
		else {
			return max(segment_range_query(at->left, low_depth, at->left->high_depth),
				segment_range_query(at->right, at->right->low_depth, high_depth));
		}
	}
}

int path_max_inner(node *higher, node* lower) {
	int64_t max_val = 0;
	//assert(lower && higher);

	while (lower->chain_head != higher->chain_head) {
		segment *seg = &lower->seg;
		while (seg->parent) seg = seg->parent;
		max_val = max(max_val, segment_range_query(seg, lower->seg.low_depth, seg->high_depth));
		lower = lower->chain_head->parent;
	}
	//assert(lower && higher);

	segment *seg = &lower->seg;
	while (seg->parent) seg = seg->parent;
	max_val = max(max_val, segment_range_query(seg, lower->seg.low_depth, higher->seg.high_depth));
	return max_val;
}

int path_max(node *u, node *v) {
	if (u == v) {
		return u->seg.max_val;
	}
	else {
		node *pivot = lca(u, v);
		//assert(pivot);
		//assert(pivot->seg.low_depth <= u->seg.low_depth);
		//assert(pivot->seg.low_depth <= v->seg.low_depth);

		int ml = path_max_inner(pivot, u);
		int mr = path_max_inner(pivot, v);
		return max(ml, mr);
	}
}

void segment_update(segment *at) {
	while (at) {
		at->max_val = max(at->left->max_val, at->right->max_val);
		at = at->parent;
	}
}

int main() {
	int n, q;
	scanf("%d %d", &n, &q);

	node1 *initial = (node1*)calloc(n, sizeof(node1));
	link *links = (link*)malloc(2 * (n - 1) * sizeof(link));

	for (int i = 0; i < n; i++) {
		initial[i].id = i;
	}

	//store links
	for (int i = 0; i < n - 1; i++) {
		int ai, bi;
		scanf("%d %d", &ai, &bi);

		node1* a = &initial[ai];
		node1* b = &initial[bi];

		link* la = &links[2 * i + 0];
		link* lb = &links[2 * i + 1];

		la->next = a->connections;
		lb->next = b->connections;

		la->with = b;
		lb->with = a;

		a->num_connections++;
		b->num_connections++;

		a->connections = la;
		b->connections = lb;
	}

	node **child_links = (node**)malloc((n - 1) * sizeof(node*));
	node *processed = (node*)calloc(n, sizeof(node));
	mapping = (node**)calloc(n, sizeof(node*));

	//convert to tree, node 0 as root
	node *procp = processed; out_storage = &procp;
	node **clp = child_links; child_storage = &clp;
	
	initial[0].num_connections++; //root only has connections to children
	directify(&initial[0], NULL, 0);

	assert(procp == processed + n);
	assert(clp == child_links + (n - 1));

	free(initial); initial = NULL;
	free(links); links = NULL;

	//heavy-light decoposition
	int num_chains = 0;
	hld(&processed[0], NULL, 1, &num_chains);
	//printf("made %d chainsn", num_chains);

	//queries
	for (int i = 0; i < q; i++) {
		int t, ui, vi;
		scanf("%d %d %d", &t, &ui, &vi);

		if (t == 1) {
			node *u = mapping[ui];
			u->seg.max_val = vi;
			segment_update(u->seg.parent);
		}

		else {
			node *u = mapping[ui];
			node *v = mapping[vi];
			int val = path_max(u, v);
			printf("%d\n", val);
		}
	}

	return 0;
}

Scor obtinut: 1.0

Submission ID: 464653574

Link challenge: https://www.hackerrank.com/challenges/heavy-light-white-falcon/problem

Heavy Light White Falcon