Untitled

[Problem Description]

A department has an ID, information about the number of employees in the department, and a maximum of two sub-departments.

When restructuring the entire organization, which is in the form of a binary tree, into a total of M groups, find out whether each group can have K or fewer people.

To have M groups, you need to cut M-1 edges.

[Fig. 1] is an example of six departments. The number inside a circle represents the number of employees of a department.
When restructuring the organization into 3 groups, check whether each group can have 33 or fewer people.



[Fig. 1]

If the organization is restructured as in [Fig. 2], the largest group (departments 3, 4, and 6) has 37 employees. In this case, the above condition is not satisfied.



[Fig. 2]

However, if the organization is restructured as in [Fig. 3], each group has 33 or fewer employees. In this case, the above condition is satisfied.



[Fig. 3]

 

Implement each required function by referring to the following API description.

※ The function signature below is based on C/C++. As for other languages, refer to the provided Main and User Code.

The following is the description of API to be written in the User Code. 

void init(int mId, int mNum)

This function is called in the beginning of each test case.

Department mId is given with mNum, the number of employees in the department.

This department becomes the topmost department.

 

Parameters

mId: the department ID ( 1 ≤ mId ≤ 1,000,000,000 )

mNum: the number of employees of the department ( 1 ≤ mNum ≤ 100 )

int add(int mId, int mNum, int mParent)

Add department mID as the sub-department of department mParent.

Department mId has mNum employees.

mParent is always the ID of an existing department.

If there are 2 sub-departments of mParent already, adding a department fails. Therefore, return -1.

The ID of an already-existing department is never given as mId.

 

Parameters

mId: the department ID ( 1 ≤ mId ≤ 1,000,000,000 )

mNum: the number of employees of the department ( 1 ≤ mNum ≤ 100 )

mParent: the ID of the higher-level department ( 1 ≤ mParent ≤ 1,000,000,000 )

 

Returns

If a department is added successfully, return the sum of the number of employees of mParent and all departments below it. In other words, return the sum of the number of employees of the sub-tree whose root node is mParent.

If not, return -1.

int remove(int mId)

Delete the department with the ID of mId. All departments below mId are deleted together.

The ID of the topmost department is never given.

The ID of an already-deleted department may be given.

Return -1, if department mId does not exist.

 

Parameters

mId: the department ID ( 1 ≤ mId ≤ 1,000,000,000 )

 

Returns

If mId exists, return the sum of the number of employees of mId and all departments below it. In other words, return the sum of the number of employees of the sub-tree whose root node is mId.

If not, return -1.

int reorganize(int M, int K)

When the entire organization is restructured into M groups, check whether each group can have K or fewer employees.
If possible, return 1. If not, return 0.

 

Parameters

M: the number of groups to be restructured into ( 2 ≤ M ≤ the total number of departments )

K: the maximum number of employees of each group ( 10 ≤ K ≤ 80,000 )

 

Returns

When restructuring into M groups, if it is possible for each group to have K or fewer employees, return 1. If not, return 0.

[Example]

Let’s look into the case where functions are called as in [Table 1].

Order

Function

return

Figure

1

init(7, 26)

 

 

2

add(9, 6, 7)

32

 

3

add(1, 19, 9)

25

 

4

add(4, 5, 7)

56

 

5

add(6, 2, 4)

7

 

6

reorganize(3, 26)

1

Fig. 4

7

add(3, 30, 4)

37

 

8

reorganize(3, 32)

0

Fig. 3

9

remove(1)

19

 

10

reorganize(3, 32)

1

Fig. 5

                                                                       [Table 1]

(Order 1) Initially, a department with the ID of 7 has 26 employees.

(Order 2) A department with 6 employees and the ID of 9 is added to department 7.
The total number of employees of department 7 and all departments below it is 32.

(Order 3) A department with 19 employees and the ID of 1 is added to department 9.
The total number of employees of department 9 and all departments below it is 25.

(Order 4) A department with 5 employees and the ID of 4 is added to department 7.
The total number of employees of department 7 and all departments below it is 56.

(Order 5) A department with 2 employees and the ID of 6 is added to department 4.
The total number of employees of department 4 and all departments below it is 7.

(Order 6) [Fig. 4] shows the way to restructure the organization into 3 groups of 26 or fewer employees.
Return 1, as the restructuring satisfies the condition.



[Fig. 4]

(Order 7) A department with 30 employees and the ID of 3 is added to department 4.
The total number of employees of department 4 and all departments below it is 37.

(Order 8) When restructuring the organization into 3 groups, it is possible for each group to have a maximum of 33, but not 32 employees as in [Fig. 3].
Therefore, return 0.

(Order 9) Delete the department with the ID of 1. The sum of the number of employees of this department and all departments below it is 19.

(Order 10) [Fig. 5] shows the way to restructure the organization into 3 groups of 32 or fewer employees.
Return 1, as the restructuring satisfies the condition.



[Fig. 5]

 

[Constraints]

1. init() is called in the beginning of each test case.

2. For each test case, add() is called up to 8,000 times.

3. For each test case, remove() is called up to 1,000 times.

4. For each test case, reorganize() is called up to 1,000 times.

 

[Input and Output]

As the input and output are processed in the provided code in the Main, they are not processed separately in the User Code.

The output result for the sample input is in the format of “#TC number result.” It is the correct answer if the result is 100; it is the wrong answer if it is 0.




#define STATUS_DELETE 1
#define STATUS_NORMAL 0
typedef struct Node{
    int mId;
    int mNum;
    Node* parent;
    Node* childs[2];
    int total;
    int status;
    Node* hashNext;
}Node;
#define MAX_N 8001
Node nodes[MAX_N];
Node* hashTable[MAX_N];
int size = 0;
int groups;
int possible;
Node* root = nodes;
int deptCnt;
int getHash(int mId) {
    return mId % MAX_N;
}
Node* findNode(int mId) {
    int hIdx = getHash(mId);
    Node* n = hashTable[hIdx];
    while (n != 0) {
        if (n->mId == mId) return n;
        n = n->hashNext;
    }
    return 0;
}
void initNode(Node* n,int mId, int mNum) {
    n->childs[0] = n->childs[1] = 0;
    n->status = STATUS_NORMAL;
    n->parent = 0;
    n->mId = mId;
    n->mNum = mNum;
    n->hashNext = 0;
    n->total = mNum;
}
void init(int mId, int mNum) {
    deptCnt = 1;
    initNode(root, mId, mNum);
    //init hashTable
    size = 1;
    for (int i = 0; i < MAX_N; i++) {
        hashTable[i] = 0;
    }
    int hIdx = getHash(mId);
    hashTable[hIdx] = root;
    return;
}
void updateTotal(Node* p, int mNum) {
    // update total
    while (p != 0) {
        p->total += mNum;
        p = p->parent;
    }
}
int add(int mId, int mNum, int mParent) {
    //check parent
    Node *p = findNode(mParent);
    if (p->childs[0] != 0 && p->childs[1] != 0) return -1;
    deptCnt++;
    Node* n = &nodes[size++];
    initNode(n, mId, mNum);
    //update hashTable
    int hIdx = getHash(mId);
    n->hashNext = hashTable[hIdx];
    hashTable[hIdx] = n;
    if (p->childs[0] == 0) p->childs[0] = n;
    else p->childs[1] = n;
    n->parent = p;
    updateTotal(p, mNum);
    return p->total;
}
void removeNode(Node* n) {
    if (n == 0) return;
    n->status = STATUS_DELETE;   
    deptCnt--;
    removeNode(n->childs[0]);
    removeNode(n->childs[1]);
}
int remove(int mId) {
    Node* n = findNode(mId);
    if (n == 0) return -1;
    if (n->status == STATUS_DELETE) return -1;
    removeNode(n);
    if (n->parent->childs[0] == n) n->parent->childs[0] = 0;
    else n->parent->childs[1] = 0;
    //update parent total
    updateTotal(n->parent, n->total * (-1));
    return n->total;
}
int reverse(Node* n, int K) {
    if (n == 0) return 0;
    if (possible == 0) return 0;
    if (n->mNum > K) {
        possible = 0;
        return 0;
    }
    // this sub tree is smaller than K
    if (n->total <= K) return n->total;
    int leftL = reverse(n->childs[0], K);
    int leftR = reverse(n->childs[1], K);
    if (n->mNum + leftL + leftR <= K) {
        return n->mNum + leftL + leftR;
    }else   if (n->mNum + leftL > K && n->mNum + leftR > K) {
        groups += 2;
        return n->mNum;
    }   
    groups++;
    return leftL < leftR ? n->mNum + leftL : n->mNum + leftR;
}
int reorganize(int M, int K) {
     
 
    if (deptCnt < M) return 0;
    possible = 1;
    groups = 0;
    reverse(root, K);
    if (possible == 0) return 0;
    if (groups < M) return 1;
    return 0;
}




#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

extern void init(int mId, int mNum);
extern int add(int mId, int mNum, int mParent);
extern int remove(int mId);
extern int reorganize(int M, int K);

/////////////////////////////////////////////////////////////////////////

#define CMD_INIT 1
#define CMD_ADD 2
#define CMD_REMOVE 3
#define CMD_REORGANIZE 4

static bool run() {
	int q;
	scanf("%d", &q);

	int mid, mnum, mparent, m, 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 %d", &mid, &mnum);
				init(mid, mnum);
				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_REORGANIZE:
				scanf("%d %d %d", &m, &k, &ans);
				ret = reorganize(m, 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;
}