Submission #1689062
Source Code Expand
#include <stdio.h>
#include <stdlib.h>
#define datatype int
typedef struct edge_sub edge;
typedef struct {
int num;
int nearnum;
edge *near;
}vertex_sub;
struct edge_sub{
vertex_sub *v;
int w;
edge *next;
};
typedef struct v_sub vertex;
struct v_sub{
int num;
datatype val;
vertex *parent;
int pareweight;
int chilnum;
vertex **children;
int *chilweight;
};
typedef struct {
int N;
int root;
vertex_sub **v_s;
vertex **v;
vertex **sorted_v;
}tree;
//頂点数N, 根の番号root, 各頂点の初期値ini_valの木を作る
tree *make_tree(int N, int root, datatype ini_val){
int i;
tree *t = (tree *)malloc(sizeof(tree));
t->N = N;
t->root = root;
t->v_s = (vertex_sub **)malloc(sizeof(vertex_sub *) * N);
t->v = (vertex **)malloc(sizeof(vertex *) * N);
t->sorted_v = (vertex **)malloc(sizeof(vertex *) * N);
vertex *parent_in_law = (vertex *)malloc(sizeof(vertex));
parent_in_law->num = -1;
parent_in_law->val = ini_val;
parent_in_law->parent = NULL;
parent_in_law->pareweight = -1;
parent_in_law->chilnum = 0;
parent_in_law->children = NULL;
parent_in_law->chilweight = NULL;
for(i = 0; i < N; i++){
(t->v_s)[i] = (vertex_sub *)malloc(sizeof(vertex_sub));
(t->v_s)[i]->num = i;
(t->v_s)[i]->nearnum = 0;
(t->v_s)[i]->near = NULL;
(t->v)[i] = (vertex *)malloc(sizeof(vertex));
(t->v)[i]->num = i;
(t->v)[i]->val = ini_val;
(t->v)[i]->parent = parent_in_law;
(t->v)[i]->pareweight = -1;
(t->v)[i]->chilnum = 0;
(t->v)[i]->children = NULL;
(t->v)[i]->chilweight = NULL;
(t->sorted_v)[i] = NULL;
}
return t;
}
//木tの頂点aと頂点bの間に重みwの無向辺を張る (0 <= a, b <= N - 1)
void set_edge(tree *t, int a, int b, int w){
edge *new1 = (edge *)malloc(sizeof(edge));
new1->v = (t->v_s)[b];
new1->w = w;
new1->next = (t->v_s)[a]->near;
(t->v_s)[a]->near = new1;
(t->v_s)[a]->nearnum++;
edge *new2 = (edge *)malloc(sizeof(edge));
new2->v = (t->v_s)[a];
new2->w = w;
new2->next = (t->v_s)[b]->near;
(t->v_s)[b]->near = new2;
(t->v_s)[b]->nearnum++;
}
//set_edge後に呼び出す
void build_tree(tree *t){
int i, j;
vertex_sub **v_s = t->v_s;
vertex **v = t->v;
vertex **sorted_v = t->sorted_v;
sorted_v[0] = v[t->root];
vertex *nowv;
edge *nowe;
for(i = 0, j = 1; j - i > 0; i++){
nowv = sorted_v[i];
if(i == 0){
v_s[nowv->num]->nearnum++;
}
nowv->children = (vertex **)malloc(sizeof(vertex *) * (v_s[nowv->num]->nearnum - 1));
nowv->chilweight = (int *)malloc(sizeof(int) * (v_s[nowv->num]->nearnum - 1));
if(i == 0){
v_s[nowv->num]->nearnum--;
}
for(nowe = v_s[nowv->num]->near; nowe != NULL; nowe = nowe->next){
if(nowe->v->num != nowv->parent->num){
(nowv->children)[nowv->chilnum] = v[nowe->v->num];
(nowv->chilweight)[nowv->chilnum] = nowe->w;
nowv->chilnum++;
v[nowe->v->num]->parent = nowv;
v[nowe->v->num]->pareweight = nowe->w;
sorted_v[j] = v[nowe->v->num];
j++;
}
}
}
}
#define keytype int
//#define datatype int
//static int malloc_cont;
//static int free_cont;
typedef struct node_sub{
keytype key; //添え字
datatype val; //値
int ele_num; //木に含まれる要素数
int height; //木の高さ
struct node_sub *left; //左の子へのポインタ
struct node_sub *right; //右の子へのポインタ
}node;
typedef struct {
node *root;
}AVL_tree;
int max(int a, int b){
if(a > b){
return a;
}
else{
return b;
}
}
//比較関数
//a < b なら負の値
//a = b なら0
//a > b なら正の値
int compare(keytype a, keytype b){
return a - b;
}
int ele_num(node *r){
if(r == NULL){
return 0;
}
else{
return r->ele_num;
}
}
int height(node *r){
if(r == NULL){
return 0;
}
else{
return r->height;
}
}
//tの指すノードを開放する
//datatypeなどがポインタ型の時はそれもfreeする
void release(node *r){
free(r);
// free_cont++;
}
node *build_node(keytype key, datatype val, node *left, node *right){
node *newr;
int left_h = height(left);
int right_h = height(right);
if(left_h > right_h + 1){
node *ll = left->left;
node *lr = left->right;
if(height(ll) < height(lr)){
newr = build_node(lr->key, lr->val, build_node(left->key, left->val, ll, lr->left), build_node(key, val, lr->right, right));
release(lr);
}
else{
newr = build_node(left->key, left->val, ll, build_node(key, val, lr, right));
}
release(left);
}
else if(right_h > left_h + 1){
node *rr = right->right;
node *rl = right->left;
if(height(rr) < height(rl)){
newr = build_node(rl->key, rl->val, build_node(key, val, left, rl->left), build_node(right->key, right->val, rl->right, rr));
release(rl);
}
else{
newr = build_node(right->key, right->val, build_node(key, val, left, rl), rr);
}
release(right);
}
else{
// malloc_cont++;
newr = (node *)malloc(sizeof(node));
newr->key = key;
newr->val = val;
newr->ele_num = ele_num(left) + ele_num(right) + 1;
newr->height = max(left_h, right_h) + 1;
newr->left = left;
newr->right = right;
}
return newr;
}
node *find_sub(keytype key, node *r){
if(r == NULL){
return NULL;
}
int comp = compare(key, r->key);
if(comp == 0){
return r;
}
else if(comp < 0){
return find_sub(key, r->left);
}
else{
return find_sub(key, r->right);
}
}
node *kth_smallest_sub(int k, node *r){
if(r == NULL || k < 1){
printf("In function 'kth_smallest_sub':\nargument 'k' is out of range\n");
return NULL;
}
else if(r->ele_num < k){
printf("In function 'kth_smallest_sub':\nargument 'k' is out of range\n");
return NULL;
}
else if(ele_num(r->left) == k - 1){
return r;
}
else if(ele_num(r->left) > k - 1){
return kth_smallest_sub(k, r->left);
}
else{
return kth_smallest_sub(k - ele_num(r->left) - 1, r->right);
}
}
int num_less_than_sub(keytype key, node *r){
if(r == NULL){
return 0;
}
else if(compare(key, r->key) < 0){
return num_less_than_sub(key, r->left);
}
else{
return ele_num(r->left) + num_less_than_sub(key, r->right) + 1;
}
}
node *next_largest_sub(keytype key, node *r){
if(r == NULL){
return NULL;
}
else if(compare(key, r->key) <= 0){
return next_largest_sub(key, r->left);
}
else{
node *candidate = next_largest_sub(key, r->right);
if(candidate == NULL){
return r;
}
else{
return candidate;
}
}
}
node *next_smallest_sub(keytype key, node *r){
if(r == NULL){
return NULL;
}
else if(compare(key, r->key) >= 0){
return next_smallest_sub(key, r->right);
}
else{
node *candidate = next_smallest_sub(key, r->left);
if(candidate == NULL){
return r;
}
else{
return candidate;
}
}
}
node *insert_sub(keytype key, datatype val, node *r){
node *newr;
if(r == NULL){
newr = build_node(key, val, NULL, NULL);
}
else{
int comp = compare(key, r->key);
if(comp == 0){
printf("In function 'insert_sub':\nkey '%d' already exists\n", key);
newr = build_node(r->key, val, r->left, r->right);
}
else if(comp < 0){
newr = build_node(r->key, r->val, insert_sub(key, val, r->left), r->right);
}
else{
newr = build_node(r->key, r->val, r->left, insert_sub(key, val, r->right));
}
release(r);
}
return newr;
}
node *erase_sub(keytype key, node *r){
node *newr;
if(r == NULL){
printf("In function 'erase_sub':\nkey '%d' doesn't exist\n", key);
newr = NULL;
}
else{
int comp = compare(key, r->key);
if(comp == 0){
if(r->left == NULL && r->right == NULL){
newr = NULL;
}
else if(r->right == NULL){
newr = r->left;
}
else if(r->left == NULL){
newr = r->right;
}
else{
node *next_larger = kth_smallest_sub(1, r->right);
newr = build_node(next_larger->key, next_larger->val, r->left, erase_sub(next_larger->key, r->right));
}
}
else if(comp < 0){
newr = build_node(r->key, r->val, erase_sub(key, r->left), r->right);
}
else{
newr = build_node(r->key, r->val, r->left, erase_sub(key, r->right));
}
release(r);
}
return newr;
}
void storeall_sub(keytype *array, int k, node *r){
if(r != NULL){
storeall_sub(array, k, r->left);
array[k + ele_num(r->left)] = r->key;
storeall_sub(array, k + ele_num(r->left) + 1, r->right);
}
}
void outall_sub(node *r){
if(r != NULL){
outall_sub(r->left);
printf("(key, val, ele_num, height) = (%d, %d, %d, %d)\n", r->key, r->val, r->ele_num, r->height);
outall_sub(r->right);
}
}
//AVL_treeを生成する
AVL_tree *make_AVL_tree(){
AVL_tree *t = (AVL_tree *)malloc(sizeof(AVL_tree));
t->root = NULL;
return t;
}
//tに含まれるノードの数を返す
int element_num(AVL_tree *t){
return ele_num(t->root);
}
//添え字がkeyのノードへのポインタを返す
//なければNULLを返す
node *find(keytype key, AVL_tree *t){
return find_sub(key, t->root);
}
//小さい順にk番目のkeyのノードへのポインタを返す
//1 ≦ k ≦ ele_num(t->root) を満たさない場合はNULLを返す(メッセージが出る)
node *kth_smallest(int k, AVL_tree *t){
return kth_smallest_sub(k, t->root);
}
//添え字がkey以下のノードの数を返す
int num_less_than(keytype key, AVL_tree *t){
return num_less_than_sub(key, t->root);
}
//keyよりも小さい中で最大の添え字のノードへのポインタを返す
//なければNULLを返す
node *next_largest(keytype key, AVL_tree *t){
return next_largest_sub(key, t->root);
}
//keyよりも大きい中で最小の添え字のノードへのポインタを返す
//なければNULLを返す
node *next_smallest(keytype key, AVL_tree *t){
return next_smallest_sub(key, t->root);
}
//添え字key, 値valのノードを挿入する
//既に存在する場合は値が上書きされる(メッセージが出る)
void insert(keytype key, datatype val, AVL_tree *t){
t->root = insert_sub(key, val, t->root);
}
//添え字keyのノードを削除する
//存在しない場合は何もしない(メッセージが出る)
void erase(keytype key, AVL_tree *t){
t->root = erase_sub(key, t->root);
}
//全ノードのkeyを小さい順に格納した配列を返す
keytype *storeall(AVL_tree *t){
keytype *array = (keytype *)malloc(sizeof(keytype) * element_num(t));
storeall_sub(array, 0, t->root);
return array;
}
//全ノードの中身をkeyの小さい順に出力する
void outall(AVL_tree *t){
outall_sub(t->root);
}
int main(){
int N, X, a, b, c, i;
long long ans = 0;
scanf("%d%d", &N, &X);
tree *t = make_tree(N, 0, 0);
for(i = 1; i < N; i++){
scanf("%d%d%d", &a, &b, &c);
set_edge(t, a - 1, b - 1, c);
}
build_tree(t);
vertex *nowv;
for(i = 1; i < N; i++){
nowv = t->sorted_v[i];
nowv->val = nowv->parent->val ^ nowv->pareweight;
}
AVL_tree *AVLt = make_AVL_tree();
node *r;
for(i = 0; i < N; i++){
nowv = t->v[i];
r = find(nowv->val ^ X, AVLt);
if(r != NULL){
ans += r->val;
}
r = find(nowv->val, AVLt);
if(r == NULL){
insert(nowv->val, 1, AVLt);
}
else{
r->val++;
}
}
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time
2017-10-16 21:45:45+0900
Task
C - エックスオア多橋君
User
abc050
Language
C (GCC 5.4.1)
Score
100
Code Size
11402 Byte
Status
AC
Exec Time
183 ms
Memory
27520 KB
Compile Error
./Main.c: In function ‘main’:
./Main.c:450:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &X);
^
./Main.c:453:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
100 / 100
Status
Set Name
Test Cases
Sample
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt
Case Name
Status
Exec Time
Memory
subtask0_sample_01.txt
AC
1 ms
128 KB
subtask0_sample_02.txt
AC
1 ms
128 KB
subtask0_sample_03.txt
AC
1 ms
128 KB
subtask1_01.txt
AC
1 ms
128 KB
subtask1_02.txt
AC
1 ms
384 KB
subtask1_03.txt
AC
183 ms
27520 KB
subtask1_04.txt
AC
183 ms
27520 KB
subtask1_05.txt
AC
182 ms
27520 KB
subtask1_06.txt
AC
50 ms
22784 KB
subtask1_07.txt
AC
77 ms
22912 KB
subtask1_08.txt
AC
78 ms
22912 KB
subtask1_09.txt
AC
104 ms
23680 KB
subtask1_10.txt
AC
106 ms
23680 KB
subtask1_11.txt
AC
1 ms
384 KB
subtask1_12.txt
AC
1 ms
384 KB
subtask1_13.txt
AC
95 ms
22912 KB
subtask1_14.txt
AC
91 ms
22912 KB
subtask1_15.txt
AC
11 ms
2816 KB
subtask1_16.txt
AC
11 ms
2816 KB
subtask1_17.txt
AC
11 ms
2816 KB
subtask1_18.txt
AC
11 ms
2816 KB
subtask1_19.txt
AC
11 ms
2816 KB
subtask1_20.txt
AC
11 ms
2816 KB
subtask1_21.txt
AC
11 ms
2816 KB
subtask1_22.txt
AC
11 ms
2816 KB
subtask1_23.txt
AC
11 ms
2816 KB
subtask1_24.txt
AC
11 ms
2816 KB