Untitled
plain_text
2 months ago
5.7 kB
1
Indexable
Never
//user constexpr int MAX_NODE = 18000; constexpr int HASH_SIZE = 30000; struct Node { Node* parent; Node* child[3]; int num; bool valid; } NodePool[MAX_NODE]; int PoolCnt, GroupCnt; struct HashNode { int key; Node* data; } HashTbl[HASH_SIZE]; Node* hashFind(int key) { unsigned long h = key % HASH_SIZE; int cnt = HASH_SIZE; while (HashTbl[h].key != 0 && cnt--) { if (HashTbl[h].key == key) { return HashTbl[h].data; } h = (h + 1) % HASH_SIZE; } return nullptr; } void hashAdd(int key, Node* data) { unsigned long h = key % HASH_SIZE; while (HashTbl[h].key != 0) { if (HashTbl[h].key == key) { HashTbl[h].data = data; return; } h = (h + 1) % HASH_SIZE; } HashTbl[h].key = key; HashTbl[h].data = data; } void delNode(Node* node) { if (node == nullptr) return; node->valid = false; for (int i = 0; i < 3; ++i) delNode(node->child[i]); } void init(int N, int mId[], int mNum[]) { PoolCnt = 0; for (int i = 0; i < HASH_SIZE; ++i) { HashTbl[i].key = 0; } GroupCnt = N; for (int i = 0; i < N; ++i) { Node* node = &NodePool[PoolCnt++]; hashAdd(mId[i], node); node->valid = true; node->parent = nullptr; node->child[0] = node->child[1] = node->child[2] = nullptr; node->num = mNum[i]; } } int add(int mId, int mNum, int mParent) { Node* node = &NodePool[PoolCnt++]; Node* parent = hashFind(mParent); if (parent->child[0] == nullptr) { parent->child[0] = node; } else if (parent->child[1] == nullptr) { parent->child[1] = node; } else if (parent->child[2] == nullptr) { parent->child[2] = node; } else { return -1; } Node* curr = parent; while (curr) { curr->num += mNum; curr = curr->parent; } hashAdd(mId, node); node->valid = true; node->parent = parent; node->child[0] = node->child[1] = node->child[2] = nullptr; node->num = mNum; return parent->num; } int remove(int mId) { Node* node = hashFind(mId); if (!node || !node->valid) { return -1; } Node* parent = node->parent; if (parent->child[0] == node) { parent->child[0] = nullptr; } else if (parent->child[1] == node) { parent->child[1] = nullptr; } else if (parent->child[2] == node) { parent->child[2] = nullptr; } Node* curr = parent; while (curr) { curr->num -= node->num; curr = curr->parent; } delNode(node); return node->num; } int distribute(int K) { int low = 1, high = 0; for (int i = 0; i < GroupCnt; ++i) { if (NodePool[i].num > high) high = NodePool[i].num; } while (low <= high) { int mid = (low + high) / 2; int sum = 0; for (int i = 0; i < GroupCnt; ++i) { if (NodePool[i].num <= mid) sum += NodePool[i].num; else sum += mid; } if (sum <= K) { low = mid + 1; } else { high = mid - 1; } } return high; } //main #ifndef _CRT_SECURE_NO_WARNINGS #define _CRT_SECURE_NO_WARNINGS #endif #include <stdio.h> extern void init(int N, int mId[], int mNum[]); extern int add(int mId, int mNum, int mParent); extern int remove(int mId); extern int distribute(int K); ///////////////////////////////////////////////////////////////////////// #define CMD_INIT 1 #define CMD_ADD 2 #define CMD_REMOVE 3 #define CMD_DISTRIBUTE 4 static bool run() { int q; scanf("%d", &q); static int midArr[1000], mnumArr[1000]; int mid, mnum, mparent, n, k; int cmd, ans, ret = 0; bool okay = false; for (int i = 0; i < q; ++i) { scanf("%d", &cmd); switch (cmd) { case CMD_INIT: scanf("%d", &n); for (int j = 0; j < n; ++j) { scanf("%d %d", &midArr[j], &mnumArr[j]); } init(n, midArr, mnumArr); okay = true; break; case CMD_ADD: scanf("%d %d %d %d", &mid, &mnum, &mparent, &ans); ret = add(mid, mnum, mparent); if (ans != ret) okay = false; break; case CMD_REMOVE: scanf("%d %d", &mid, &ans); ret = remove(mid); if (ans != ret) okay = false; break; case CMD_DISTRIBUTE: scanf("%d %d", &k, &ans); ret = distribute(k); if (ans != ret) okay = false; break; default: okay = false; break; } } return okay; } int main() { setbuf(stdout, NULL); //freopen("sample_input.txt", "r", stdin); int T, MARK; scanf("%d %d", &T, &MARK); for (int tc = 1; tc <= T; tc++) { int score = run() ? MARK : 0; printf("#%d %d\n", tc, score); } return 0; } //input 25 100 12 1 3 7 25 4 5 2 40 2 3 5 4 10 2 9 5 7 30 2 1 15 4 25 2 8 10 1 25 4 100 35 2 6 20 4 55 4 109 39 2 5 20 9 25 4 131 45 3 1 25 4 110 40 30 1 3 6932607 76 9283574 79 3799193 94 2 639546083 72 9283574 151 2 7490781 42 3799193 136 2 6568711 8 3799193 144 2 572001 54 7490781 96 2 3518315 8 7490781 104 2 2144677 10 3799193 216 2 2988431 28 9283574 179 2 5269673 6 3518315 14 4 463 208 2 2948033 98 6568711 106 2 973693771 88 2144677 98 4 551 296 2 5289891 12 5269673 18 2 6859805 6 5269673 24 2 4425671 76 973693771 164 2 339118881 86 5269673 110 2 6955307 44 5289891 56 3 973693771 164 4 666 411 2 231882 47 6859805 53 4 647 392 2 9653352 5 572001 59 2 9669600 9 6568711 115 3 5289891 56 2 106931781 50 5269673 195 2 9415005 2 9669600 11 3 6955307 -1 2 441886 51 339118881 137 2 2048342 75 441886 126