Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.4 kB
1
Indexable
Never
#include <unordered_map>
#include <string>
#include <set>
using namespace std;
 
struct Bacteria
{
    int Gen;
    string Parent;
    int Firstday;
    int Lastday;
    int num_child;
    string Path;
};
 
unordered_map<string, Bacteria> Family;
int Count1[1005]={};
int Count2[1000005]={};
 
void update(int Start, int End)
{
    int x = Start/1000;
    int y = End/1000;
    for (int i = x+1; i < y; i++)
    {
        Count1[i]++;
    }
    if (x==y)
    {
        for (int i = Start; i <= End; i++)
        {
            Count2[i]++;
        }
    }
    else
    {
        for (int i = Start; i < (x+1)*1000; i++)
        {
            Count2[i]++; //phan le dau
        }
        for (int i = y*1000; i <= End; i++)
        {
            Count2[i]++; // phan le duoi
        } 
    }
}
 
void init(char mAncestor[], int mDeathday)
{
    Family.clear();
 
    for (int i = 0; i < 1005; i++)
    {
        Count1[i] =0;
         
    }
    for (int i = 0; i < 1000002; i++)
    {
        Count2[i] =0;
    }
     
    Bacteria ancestor;
    ancestor.Gen = 0;
    ancestor.Parent = mAncestor;
    ancestor.Firstday = 0;
    ancestor.Lastday = mDeathday;
    ancestor.num_child = 0;
    ancestor.Path ="0";
    string name = mAncestor;
    Family[name] = ancestor;
    update(0,mDeathday);
    return;
}
 
int add(char mName[], char mParent[], int mBirthday, int mDeathday)
{
    Bacteria child;
    child.Gen = Family[mParent].Gen +1;
    child.Parent = mParent;
    child.Firstday = mBirthday;
    child.Lastday = mDeathday;
    child.num_child = 0;
 
    Family[mParent].num_child++;
    child.Path = Family[mParent].Path + to_string(Family[mParent].num_child);
    Family[mName] = child;
    update(mBirthday,mDeathday);
    return child.Gen;
}
 
int distance(char mName1[], char mName2[])
{
    string name1 = mName1;
    string name2 = mName2;
    if(name1 == name2) return 0;
    int gen1 = Family[name1].Gen;
    int gen2 = Family[name2].Gen;
    if(gen1 == 0) return gen2;
    if(gen2 == 0) return gen1;
    string path1 = Family[name1].Path;
    string path2 = Family[name2].Path;
    int i =1, count=0;
    while (path1[i] == path2[i])
    {
        count++;
        i++;
    }
    return gen1 + gen2 - 2*count;
}
 
int count(int mDay)
{
    int ret = Count1[mDay/1000] + Count2[mDay];
     
    return ret;
}