Untitled
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...