#include #include 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); } }