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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | typedef unsigned long long ULL; const int LM = 205; const int MOD = 256; int idcnt, bcnt; int distTab[LM][LM], member[LM][2]; struct Node { ULL key; int id, gender, pid; Node*next; Node* alloc(ULL nk, int nid, int ng, int npid, Node*np) { key = nk, id = nid, gender = ng, pid = npid, next = np; return this; } }buf[LM], *htab[MOD]; ULL hashF(char*s, ULL key = 0) { for (int i = 0; s[i]; ++i) key = key * 27 + s[i] - 96; return key; } void push(char name[], int id, int g, int pid) { ULL key = hashF(name); int hidx = key & 255; ++bcnt; htab[hidx] = buf[bcnt].alloc(key, id, g, pid, htab[hidx]); member[id][g] = bcnt; /// ***** } Node* probing(char exname[]) { ULL key = hashF(exname); int hidx = key & 255; Node*p = htab[hidx], *ret = NULL; int cnt = 0; for (; p; p = p->next) { if (p->key == key) { cnt++; ret = p; } } if (cnt > 1) { int debug = 1; } return ret; } void init(char initName[], int initGender) { idcnt = bcnt = 0; for (int i = 0; i < LM; ++i) { member[i][0] = member[i][1] = 0; for (int j = 0; j < LM; ++j) distTab[i][j] = 0; } for (int i = 0; i < MOD; ++i) htab[i] = NULL; push(initName, ++idcnt, initGender, 0); } void update(int exid, int newid) { for (int i = 1; i < idcnt; ++i) { distTab[newid][i] = distTab[exid][i] + 1; distTab[i][newid] = distTab[exid][i] + 1; } } bool addMember(char newName[], int newGender, int kindShip, char existingName[]) { Node*p = probing(existingName); if (p == NULL) { int debug = 1; } if (kindShip == 0) { if (member[p->id][newGender]) return 0; /// ***** push(newName, p->id, newGender, 0); } else if (kindShip == 1) { if (p->pid) { /// 기존멤버에 부모가 있는 경우 if (member[p->pid][newGender]) return 0; push(newName, p->pid, newGender, 0); } else { /// 기존멤버에 처음 등장하는 부모 push(newName, ++idcnt, newGender, 0); p->pid = idcnt; update(p->id, idcnt); } } else { push(newName, ++idcnt, newGender, p->id); update(p->id, idcnt); } return 1; } int getDistance(char nameA[], char nameB[]) { int aid = probing(nameA)->id, bid = probing(nameB)->id; return distTab[aid][bid]; } int countMember(char name[], int dist) { Node*p = probing(name); int ret = 0; if (dist == 0) { if (member[p->id][!p->gender]) return 1; return 0; } for (int i = 1; i <= idcnt; ++i) { if (distTab[p->id][i] == dist) { if (member[i][0]) ret++; if (member[i][1]) ret++; } } return ret; } | cs |