Submission #58114067

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
struct node_s {
  int exists;
  struct node_s* next[2];
};
struct map_s {
  int elem_count;
  struct node_s* root;
};
/* 追加した場合は1、既にある場合は0を返す */
int map_add_i(struct node_s** node, int key) {
  if (*node == NULL) {
    *node = malloc(sizeof(**node));
    if (*node == NULL) exit(2);
    **node = (struct node_s){0, {NULL, NULL}};
  }
  if (key == 0) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

struct node_s {
	int exists;
	struct node_s* next[2];
};

struct map_s {
	int elem_count;
	struct node_s* root;
};

/* 追加した場合は1、既にある場合は0を返す */
int map_add_i(struct node_s** node, int key) {
	if (*node == NULL) {
		*node = malloc(sizeof(**node));
		if (*node == NULL) exit(2);
		**node = (struct node_s){0, {NULL, NULL}};
	}
	if (key == 0) {
		int ret = !(*node)->exists;
		(*node)->exists = 1;
		return ret;
	} else {
		return map_add_i(&(*node)->next[key & 1], key >> 1);
	}
}

void map_add(struct map_s* map, int key) {
	if (map_add_i(&map->root, key)) map->elem_count++;
}

void map_iter_i(struct node_s* node, int key, int depth, void* data, void (*func)(void* data, int key)) {
	if (node != NULL) {
		if (node->exists) func(data, key);
		map_iter_i(node->next[0], key, depth + 1, data, func);
		map_iter_i(node->next[1], key | (1 << depth), depth + 1, data, func);
	}
}

void map_iter(struct map_s* map, void* data, void (*func)(void* data, int key)) {
	map_iter_i(map->root, 0, 0, data, func);
}

void map_clear_i(struct node_s* node) {
	if (node != NULL) {
		map_clear_i(node->next[0]);
		map_clear_i(node->next[1]);
		free(node);
	}
}

void map_clear(struct map_s* map) {
	map_clear_i(map->root);
	map->elem_count = 0;
	map->root = NULL;
}

int N, Q;
int C[212345];
int a[212345], b[212345];

struct map_s hako[212345];

void add_func(void* data, int key) {
	map_add(data, key);
}

int main(void) {
	int i;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	for (i = 1; i <= N; i++) {
		if (scanf("%d", &C[i]) != 1) return 1;
	}
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d", &a[i], &b[i]) != 2) return 1;
	}

	for (i = 1; i <= N; i++) {
		map_add(&hako[i], C[i]);
	}

	for (i = 0; i < Q; i++) {
		if (hako[a[i]].elem_count <= hako[b[i]].elem_count) {
			map_iter(&hako[a[i]], &hako[b[i]], add_func);
			map_clear(&hako[a[i]]);
		} else {
			struct map_s temp;
			map_iter(&hako[b[i]], &hako[a[i]], add_func);
			map_clear(&hako[b[i]]);
			temp = hako[a[i]];
			hako[a[i]] = hako[b[i]];
			hako[b[i]] = temp;
		}
		printf("%d\n", hako[b[i]].elem_count);
	}
	return 0;
}

/*

各箱にはいっているボールの色の集合を管理する
要素数の少ない方を走査して大きい方に突っ込めば多分なんとかなる (予想)

*/

Submission Info

Judge Result