Submission #74591902

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
struct dict_node {
  int value;
  struct dict_node* next[2];
};
void dict_set(struct dict_node** proot, int key, int value) {
  if (*proot == NULL) {
    *proot = malloc(sizeof(**proot));
    if (*proot == NULL) exit(2);
    **proot = (struct dict_node){ -1, { NULL, NULL }};
  }
  if (key == 0) {
    (*proot)->value = value;
  } else {
    dict_set(&(*proot)->next[key & 1], key >> 1, value);
  }
}
int dict_get(const struct dict_node* root, int key) {
  if (root == NULL) return -1;
  if (key == 0) return root->value;
  return dict_get(root->next[key & 1], key >> 1);
}
struct node_s;
struct child_s {
  int element;
  struct node_s* next;
};
struct node_s {
  int id_num;
  int* id;
  int children_num;
  struct child_s* children;
  struct dict_node* children_indice;
};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

struct dict_node {
	int value;
	struct dict_node* next[2];
};

void dict_set(struct dict_node** proot, int key, int value) {
	if (*proot == NULL) {
		*proot = malloc(sizeof(**proot));
		if (*proot == NULL) exit(2);
		**proot = (struct dict_node){ -1, { NULL, NULL }};
	}
	if (key == 0) {
		(*proot)->value = value;
	} else {
		dict_set(&(*proot)->next[key & 1], key >> 1, value);
	}
}

int dict_get(const struct dict_node* root, int key) {
	if (root == NULL) return -1;
	if (key == 0) return root->value;
	return dict_get(root->next[key & 1], key >> 1);
}

struct node_s;

struct child_s {
	int element;
	struct node_s* next;
};

struct node_s {
	int id_num;
	int* id;
	int children_num;
	struct child_s* children;
	struct dict_node* children_indice;
};

struct node_s root;

int N;
int x[312345], y[312345];

struct node_s* nodes[312345];

int cmp_int(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (a > b) - (a < b);
}

int cmp_child(const void* x, const void* y) {
	struct child_s a = *(const struct child_s*)x, b = *(const struct child_s*)y;
	return (a.element > b.element) - (a.element < b.element);
}

int elem_exists = 0;

/* 行きがけ順で添え字を出力する */
void dfs(struct node_s* node) {
	int i;
	if (node->id_num > 0) {
		qsort(node->id, node->id_num, sizeof(*node->id), cmp_int);
		for (i = 0; i < node->id_num; i++) {
			if (elem_exists) putchar(' ');
			printf("%d", node->id[i]);
			elem_exists = 1;
		}
	}
	if (node->children_num > 0) {
		qsort(node->children, node->children_num, sizeof(*node->children), cmp_child);
		for (i = 0; i < node->children_num; i++) {
			dfs(node->children[i].next);
		}
	}
}

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 1; i <= N; i++) {
		if (scanf("%d%d", &x[i], &y[i]) != 2) return 1;
	}
	nodes[0] = &root;
	for (i = 1; i <= N; i++) {
		struct node_s* parent = nodes[x[i]];
		int child_idx = dict_get(parent->children_indice, y[i]);
		if (child_idx >= 0) {
			/* この整数がつく数列はすでにあるので、それを参照する */
			nodes[i] = parent->children[child_idx].next;
		} else {
			/* 新しい数列を作成する */
			nodes[i] = malloc(sizeof(*nodes[i]));
			if (nodes[i] == NULL) return 2;
			*nodes[i] = (struct node_s){ 0, NULL, 0, NULL, NULL };
			/* 新しい数列をつく元の数列に接続する */
			parent->children = realloc(parent->children, sizeof(*parent->children) * (parent->children_num + 1));
			if (parent->children == NULL) return 2;
			parent->children[parent->children_num] = (struct child_s){ y[i], nodes[i] };
			dict_set(&parent->children_indice, y[i], parent->children_num);
			parent->children_num++;
		}
		/* 数列に対応する添え字を追加する */
		nodes[i]->id = realloc(nodes[i]->id, sizeof(*nodes[i]->id) * (nodes[i]->id_num + 1));
		if (nodes[i]->id == NULL) return 2;
		nodes[i]->id[nodes[i]->id_num++] = i;
	}
	dfs(&root);
	putchar('\n');
	return 0;
}

Submission Info

Judge Result