Untitled

#define MAX_D   39999
#define MAX_H   39999
#define R       register
#define FAST    __attribute((optimize("Ofast")))
   
struct DEPARTMENT
{
    int id;
    int total_count;
    int parent;
    int chldCnt;
    bool deleted;
    int hashNext;
};
   
DEPARTMENT dep[MAX_D];
int idx_dep;
int dep_count;
   
struct HASHMAP
{
    int hash[MAX_H];
    FAST void reset()
    {
        for (R int i = 0; i < MAX_H; i++)
            hash[i] = 0;
    }
   
    FAST void add(int id)
    {
        R int h = dep[id].id % MAX_H;
        dep[id].hashNext = hash[h];
        hash[h] = id;
    }
   
    FAST int get(int mid)
    {
        R int h = mid % MAX_H;
        R int id = hash[h];
        while (id && (dep[id].id != mid || dep[id].deleted))
            id = dep[id].hashNext;
        return id;
    }
};
   
HASHMAP hmp;
   
FAST void init(int N, int mId[], int mNum[])
{
    idx_dep = 1;
    hmp.reset();
    dep_count = N;
    for (R int i = 0; i < N; i++)
    {
        dep[idx_dep].id = mId[i];
        dep[idx_dep].chldCnt = 0;
        dep[idx_dep].total_count = mNum[i];
        dep[idx_dep].parent = -1;
        dep[idx_dep].deleted = false;
        dep[idx_dep].hashNext = 0;
        hmp.add(idx_dep++);
    }
}
   
FAST int add(int mId, int mNum, int mParent)
{
   
    R int pid = hmp.get(mParent);
    if (dep[pid].chldCnt == 3)
        return -1;
   
    dep[idx_dep].id = mId;
    dep[idx_dep].chldCnt = 0;
    dep[idx_dep].total_count = 0;
    dep[idx_dep].parent = pid;
    dep[idx_dep].deleted = false;
    dep[idx_dep].hashNext = 0;
    hmp.add(idx_dep);
   
    dep[pid].chldCnt++;
   
    R int tmp = idx_dep++;
    while (tmp != -1)
    {
        dep[tmp].total_count += mNum;
        tmp = dep[tmp].parent;
    }
   
    return dep[pid].total_count;
}
   
FAST int remove(int mId)
{
    if (hmp.get(mId) == 0)
        return -1;
    R int id = hmp.get(mId);
   
    dep[id].deleted = true;
    dep[dep[id].parent].chldCnt--;
   
    R int tmp = dep[id].parent;
    R int cnt = dep[id].total_count;
    while (tmp != -1)
    {
        if (dep[tmp].deleted)
            return -1;
   
        dep[tmp].total_count -= cnt;
        tmp = dep[tmp].parent;
    }
   
    return cnt;
}
   
FAST int distribute(int K)
{
   
    R int l = 1;
    R int r = 0;
    R int i,count;
    for (i = 1; i <= dep_count; i++)
        r = (r < dep[i].total_count ? dep[i].total_count : r);
   
    R int ans, m;
    while (l <= r)
    {
        m = (l + r) >> 1;
   
        count = 0;
        for (i = 1; i <= dep_count; i++)
            count += (dep[i].total_count < m ? dep[i].total_count : m);
        if (count <= K)
        {
            ans = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
   
    return ans;
}