Untitled
plain_text
2 months ago
3.9 kB
2
Indexable
Never
#include<cstring> #define ll long long #define MS 13000 #define MT 1000002 using namespace std; struct species{ int id; int pid; int st; int en; int dist; int parent1; int parent10; int parent100; ll v; int next; }S[MS]; int map[MS], nm; int h; ll uv; int getID(char *s){ ll v = 0; for (int i = 0; s[i]; i++) v = (v << 6) | (s[i] - 'A' + 1); uv = v; h = v%MS; int id = map[v%MS]; while (id && S[id].v != uv) id = S[id].next; return id; } int interval, num, single[MT]; int secs[1003]; int c; void update(int x, int delta) { x += 1; for (; x <= MT; x += x&-x) single[x] += delta; } int query(int x) { x += 1; int sum = 0; for (; x > 0; x -= x&-x) sum += single[x]; return sum; } void init(char mAncestor[], int mDeathday) { interval = 1000; for (register int i = 0; i <= MS; i++){ map[i] = 0; S[i].v = 0; S[i].next = 0; } nm = 1; c = 1; memset(single, 0, sizeof(single)); for (int i = 0; i < 10; i++) secs[i] = 0; int id = getID(mAncestor); if (!id){ S[c].id = c; S[c].en = mDeathday; S[c].pid = -1; S[c].st = 0; S[c].dist = 0; S[c].v = uv; S[c].next = map[h]; map[h] = c; //calcnt(0, mDeathday); update(0, 1); update(mDeathday+1, -1); c++; } return; } int add(char mName[], char mParent[], int mBirthday, int mDeathday) { int pid = getID(mParent); int id = getID(mName); if (!id){ id = c; S[c].id = c; S[c].en = mDeathday; S[c].pid = pid; S[c].st = mBirthday; S[c].dist = S[S[c].pid].dist + 1; S[c].parent1 = pid; if (S[pid].dist % 100 != 0) S[c].parent100 = S[pid].parent100; else S[c].parent100 = pid; if (S[pid].dist % 10 != 0) S[c].parent10 = S[pid].parent10; else S[c].parent10 = pid; //calcnt(mBirthday, mDeathday); update(mBirthday, 1); update(mDeathday+1, -1); S[c].v = uv; S[c].next = map[h]; map[h] = c; c++; } return S[id].dist; } int distance(char mName1[], char mName2[]) { //int id1 = getID(mName1);// name[mName1]; //int id2 = getID(mName2); // name[mName2]; //int d = 0; //while (id1 != id2){ // if (id1 < id2) id2 = S[id2].pid; // else id1 = S[id1].pid; // d++; //} //return d; int p1 = getID(mName1), p2 = getID(mName2), d1 = S[p1].dist, d2 = S[p2].dist; // jump 100 while (S[S[p1].parent100].dist < S[S[p2].parent100].dist) p2 = S[p2].parent100; while (S[S[p1].parent100].dist > S[S[p2].parent100].dist) p1 = S[p1].parent100; while (S[p1].parent100 != S[p2].parent100) { p2 = S[p2].parent100; p1 = S[p1].parent100; } // jump 10 while (S[S[p1].parent10].dist < S[S[p2].parent10].dist) p2 = S[p2].parent10; while (S[S[p1].parent10].dist > S[S[p2].parent10].dist) p1 = S[p1].parent10; while (S[p1].parent10 != S[p2].parent10) { p2 = S[p2].parent10; p1 = S[p1].parent10; } // jump 1 while (S[p1].dist > S[p2].dist) p1 = S[p1].parent1; while (S[p1].dist < S[p2].dist) p2 = S[p2].parent1; while (p1 != p2) { p1 = S[p1].parent1; p2 = S[p2].parent1; } return d1 + d2 - S[p1].dist - S[p2].dist; } int count(int mDay) { return query(mDay); }