106 lines
2.2 KiB
C++
106 lines
2.2 KiB
C++
|
#include <stdlib.h>
|
||
|
|
#include <stdio.h>
|
||
|
|
|
||
|
|
typedef struct tree {
|
||
|
|
struct tree* sons[27]; // at most 27
|
||
|
|
int validity; // check the fst 3 bits: 1 if valid, 0 else
|
||
|
|
} tree_t;
|
||
|
|
|
||
|
|
void free_tree(tree_t* t) {
|
||
|
|
if (!t)
|
||
|
|
return;
|
||
|
|
|
||
|
|
for (int i=0; i < 27; i++) {
|
||
|
|
free_tree(t->sons[i]);
|
||
|
|
}
|
||
|
|
|
||
|
|
free(t);
|
||
|
|
}
|
||
|
|
|
||
|
|
void count_scores(tree_t* t, int* a, int* b, int* c) {
|
||
|
|
if (t == NULL)
|
||
|
|
return;
|
||
|
|
|
||
|
|
if (t->validity == 7) {
|
||
|
|
//Nothing
|
||
|
|
} else if (t->validity == 1) {
|
||
|
|
(*a) += 3;
|
||
|
|
} else if (t->validity == 2) {
|
||
|
|
(*b) += 3;
|
||
|
|
} else if (t->validity == 4) {
|
||
|
|
(*c) += 3;
|
||
|
|
} else if (t->validity == 3) {
|
||
|
|
(*a)++; (*b)++;
|
||
|
|
} else if (t->validity == 5) {
|
||
|
|
(*a)++; (*c)++;
|
||
|
|
} else if (t->validity == 6) {
|
||
|
|
(*b)++; (*c)++;
|
||
|
|
}
|
||
|
|
|
||
|
|
for (int i=0; i < 27; i++) {
|
||
|
|
if (t->sons[i] != NULL)
|
||
|
|
count_scores(t->sons[i], a, b, c);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
void tree_add(tree_t* t, char* word, int user_id) {
|
||
|
|
if (word[0] == '\0') {
|
||
|
|
//printf("val from %d to ", t->validity);
|
||
|
|
t->validity = (t->validity) | (1 << user_id);
|
||
|
|
//printf("%d for %d\n", t->validity, user_id);
|
||
|
|
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
int letter = (int)(word[0]-'a');
|
||
|
|
|
||
|
|
if (t->sons[letter] == NULL) {
|
||
|
|
tree_t* nt = (tree_t*)malloc(sizeof(tree_t));
|
||
|
|
nt->validity = 0;
|
||
|
|
for (int i=0; i < 27; i++) {
|
||
|
|
nt->sons[i] = NULL;
|
||
|
|
}
|
||
|
|
t->sons[letter] = nt;
|
||
|
|
}
|
||
|
|
|
||
|
|
tree_add(t->sons[letter], word+1, user_id);
|
||
|
|
}
|
||
|
|
|
||
|
|
tree_t* construct_tree() {
|
||
|
|
int word_count;
|
||
|
|
scanf("%d", &word_count);
|
||
|
|
|
||
|
|
tree_t* t = (tree_t*)malloc(sizeof(tree_t));
|
||
|
|
t->validity = 0;
|
||
|
|
for (int i=0; i < 27; i++) {
|
||
|
|
t->sons[i] = NULL;
|
||
|
|
}
|
||
|
|
|
||
|
|
for (int user_id=0; user_id < 3; user_id++) {
|
||
|
|
for (int j=0; j < word_count; j++) {
|
||
|
|
char word[4];
|
||
|
|
scanf("%s", word);
|
||
|
|
|
||
|
|
tree_add(t, word, user_id);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return t;
|
||
|
|
}
|
||
|
|
|
||
|
|
int main() {
|
||
|
|
int count;
|
||
|
|
scanf("%d", &count);
|
||
|
|
|
||
|
|
for (int i = 0; i < count; i++) {
|
||
|
|
//printf("Round %d:\n", i);
|
||
|
|
tree_t* t = construct_tree();
|
||
|
|
|
||
|
|
int a, b, c;
|
||
|
|
a = b = c = 0;
|
||
|
|
count_scores(t, &a, &b, &c);
|
||
|
|
printf("%d %d %d\n", a, b, c);
|
||
|
|
|
||
|
|
free_tree(t);
|
||
|
|
}
|
||
|
|
}
|