Untitled
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; }