Untitled

 avatar
unknown
plain_text
2 years ago
2.7 kB
3
Indexable
#include <unordered_map>
  
using namespace std;
  
struct tt
{
    int id;
    int num;
    int sum;
    tt* left;
    tt* right;
    tt* par;
    int childnum;
    bool isalive;
}tnodes[80002];
  
  
int tnodecount;
unordered_map<int, tt*> mps;
  
int group;
int k;
int target;
  
void update(tt* node, int num)
{
    while (node != NULL)
    {
        node->sum += num;
        node = node->par;
    }
  
}
  
void updateDelete(tt* node)
{
    if (node == NULL)
        return;
    node->isalive = false;
    updateDelete(node->left);
    updateDelete(node->right);
}
  
void init(int mId, int mNum) {
  
    mps.clear();
    tnodecount = 0;
    mps[mId] = &tnodes[tnodecount];
    tnodes[tnodecount].left = NULL;
    tnodes[tnodecount].right = NULL;
    tnodes[tnodecount].par = NULL;
    tnodes[tnodecount].isalive = true;
    tnodes[tnodecount].childnum = 0;
    tnodes[tnodecount].sum = mNum;
    tnodes[tnodecount].num = mNum;
    tnodes[tnodecount].id = mId;
    tnodecount++;
}
  
int add(int mId, int mNum, int mParent) {
    if (mps[mParent]->childnum == 2)
        return -1;
    tt* cur = &tnodes[tnodecount];
    tt* par = mps[mParent];
    cur->id = mId;
    cur->isalive = true;
    cur->left = NULL;
    cur->right = NULL;
    cur->par = par;
    cur->num = mNum;
    cur->sum = mNum;
    cur->childnum = 0;
    if (par->left == NULL)
        par->left = cur;
    else
        par->right = cur;
    par->childnum++;
    mps[mId] = cur;
    update(par, mNum);
    tnodecount++;
    return par->sum;
}
  
int remove(int mId) {
    if (mps[mId] == NULL || mps[mId]->isalive == false)
        return -1;
    tt* cur = mps[mId];
    tt* par = cur->par;
    updateDelete(cur);
    update(par, -(cur->sum));
    par->childnum--;
    par->left == cur ? par->left = NULL : par->right = NULL;
  
    return cur->sum;
}
  
  
int DFS(tt* node)
{
    if (node == NULL)
        return 0;
    if (group > target)
        return 0;
    if (node->num > k)
    {
        group = 80001;
        return 0;
    }
  
    int left = DFS(node->left);
    int right = DFS(node->right);
  
    if (node->num + left + right <= k)
    {
        return node->num + left + right;
    }
    else if (node->num + left <= k || node->num + right <= k)
    {
        group++;
        return node->num + left < node->num + right ? node->num + left : node->num + right;
    }
  
    group += 2;
    return node->num;
}
  
int reorganize(int M, int K) {
    group = 1;
    k = K;
    target = M;
    DFS(&tnodes[0]);
    return group <= target;
}
Editor is loading...