Untitled
plain_text
2 months ago
3.7 kB
1
Indexable
Never
#define FAST __attribute((optimize("Ofast"))) #define MAX_N 12002 #define MAX_DAY 1000002 #define MAX_LOG 11 // 2 ^ 11 > 2000 (max distance from ancestor to all nodes) #define HASHSIZE 20011 struct Bacterial { long long name; int depth; Bacterial* parent; Bacterial* next; //HashMap Bacterial* ancestors[MAX_LOG]; //ancestors[i] of this bacterial is ancestors[i - 1] of its ancestors[i - 1], //which means distance between this bacterial and its ancestors[i] is: 2 ^ i } bacterials[MAX_N]; int bacterialNum; //HashMap implementation Bacterial* HashTable[HASHSIZE]; FAST long long hash(char *str) { long long val = 0; for ( ; *str; str++) val = (val << 5) + (*str & 31); //character & 31 = its position in alphabet return val; } FAST void addToMap(Bacterial* b) { int index = b->name % HASHSIZE; b->next = HashTable[index]; HashTable[index] = b; } FAST Bacterial* findInMap(long long name) { for (Bacterial* b = HashTable[name % HASHSIZE]; b; b = b->next) if (name == b->name) return b; return nullptr; } //Fenwick tree implementation int BIT[MAX_DAY]; FAST int getSum(int index) { int ret = 0; for (++index; index > 0; index -= index & (-index)) ret += BIT[index]; return ret; } FAST void updatePosition(int index, int val) { for (++index; index < MAX_DAY; index += index & (-index)) BIT[index] += val; } FAST void increaseByRange(int from, int to) { updatePosition(from, 1); updatePosition(to + 1, -1); } FAST void createNewBacterial(char mName[], Bacterial* mParent, int mDepth, int mFirstDay, int mLastDay) { Bacterial* b = &bacterials[bacterialNum++]; b->name = hash(mName); b->parent = mParent; b->depth = mDepth; b->parent = b->ancestors[0] = mParent; addToMap(b); increaseByRange(mFirstDay, mLastDay); for (register int i = 1; i < MAX_LOG; i++) b->ancestors[i] = b->ancestors[i - 1] ? b->ancestors[i - 1]->ancestors[i - 1] : nullptr; } FAST int loga(int x) { if (x == 0 || x == 1) return 0; int ret = 0; for ( ; x > 1; x >>= 1) ret++; return ret; } FAST Bacterial* lca(Bacterial* b1, Bacterial* b2) //find the lowest common ancestor { if (b1->depth < b2->depth) { register Bacterial* tmp = b1; b1 = b2; b2 = tmp; } for (register int i = loga(b1->depth); i >= 0; i--) if (b1->depth - (1 << i) >= b2->depth) b1 = b1->ancestors[i]; if (b1 == b2) return b1; for (register int i = loga(b1->depth); i >= 0; i--) { if (b1->ancestors[i] && b1->ancestors[i] != b2->ancestors[i]) { b1 = b1->ancestors[i]; b2 = b2->ancestors[i]; } } return b1->parent; } ///////////////////////// FAST void init(char mAncestor[], int mLastday) { for (register int i = 0; i < HASHSIZE; i++) HashTable[i] = nullptr; for (register int i = 0; i < MAX_DAY; i++) BIT[i] = 0; bacterialNum = 0; createNewBacterial(mAncestor, nullptr, 0, 0, mLastday); } FAST int add(char mName[], char mParent[], int mFirstday, int mLastday) { Bacterial* p = findInMap(hash(mParent)); createNewBacterial(mName, p, p->depth + 1, mFirstday, mLastday); return p->depth + 1; } FAST int distance(char mName1[], char mName2[]) { Bacterial* b1 = findInMap(hash(mName1)); Bacterial* b2 = findInMap(hash(mName2)); return b1->depth + b2->depth - 2 * lca(b1, b2)->depth; } FAST int count(int mDay) { return getSum(mDay); }