Untitled

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