Untitled

mail@pastecode.io avatarunknown
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