Untitled

unknown
plain_text
a month ago
13 kB
Indexable
Never
---------------MAIN----------------
#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;
}

---------------USER----------------
#define MAX_HASH 16003
#define MAX_DEPARTMENT 9000

class Department{
public:
	int mId, employee;
	int num;
	Department* parent, * child1, * child2;;
	Department* hashNext;
	bool isRemove;
	Department(){
		mId = employee = num = 0;
		parent = child1 = child2 = 0;
		hashNext = 0;
		isRemove = true;
	}
} departments[MAX_DEPARTMENT];

class HashMap{
public:
	Department* hash[MAX_HASH];
	void reset(){
		for(int i = 0; i < MAX_HASH; i++){
			hash[i] = 0;
		}
	}
	void insert(Department* node){
		int key = node->mId % MAX_HASH;
		node->hashNext = hash[key];
		hash[key] = node;
	}
	Department* getHash(Department* node){
		int key = node->mId % MAX_HASH;
		Department* tmp = hash[key];
		while(tmp && tmp->mId != node->mId) {
			tmp = tmp->hashNext;
		}

		return tmp;
	}
};

HashMap hashMap;
int possible;
int idx, cntCut;

void init(int mId, int mNum) {
	hashMap.reset();
	idx = 1;
	departments[idx].mId = mId;
	departments[idx].employee = mNum;
	departments[idx].num = mNum;
	departments[idx].isRemove = false;
	departments[idx].parent = 0;
	departments[idx].child1 = 0;
	departments[idx].child2 = 0;
	departments[idx].hashNext = 0;
	hashMap.insert(&departments[idx]);
	idx++;
	return;
}

int add(int mId, int mNum, int mParent) {
	departments[0].mId = mParent;
	Department* parent = hashMap.getHash(&departments[0]);
	if(parent->child1 != 0 && parent->child2 != 0) return -1;

	departments[idx].mId = mId;
	departments[idx].parent = parent;
	departments[idx].employee = mNum;
	departments[idx].num = mNum;
	departments[idx].isRemove = false;
	departments[idx].child1 = 0;
	departments[idx].child2 = 0;
	departments[idx].hashNext = 0;
	hashMap.insert(&departments[idx]);

	parent->child1 == 0 ? parent->child1 = &departments[idx] : parent->child2 = &departments[idx];
	Department* tmpParent = parent;
	while(tmpParent){
		tmpParent->employee += mNum;
		tmpParent = tmpParent->parent;
	}

	idx++;
	return parent->employee;
}

int remove(int mId) {
	departments[0].mId = mId;
	Department* cur = hashMap.getHash(&departments[0]);

	if(cur == 0 || cur->isRemove) return -1;
	int num = cur->employee;
	cur->isRemove = true;

	Department* tParent = cur->parent;
	if(tParent->child1 == cur) tParent->child1 = 0;
	else tParent->child2 = 0;

	while(tParent){
		if(tParent->isRemove == true) {
			cur->isRemove = true;
			return -1;
		}
		tParent->employee -= num;
		tParent = tParent->parent;
	}
	return num;
}

int countCut(Department* p, int K)
{
	if(p == 0 || possible == 0) return 0;
	if(p->num > K){
		possible = 0;
		return 0;
	}

	if(p->employee <= K) return p->employee;
	int left = countCut(p->child1, K);
	int right = countCut(p->child2, K);
	if(p->num + left + right <= K) return p->num + left + right;
	else if(p->num + left > K && p->num + right > K){
		cntCut += 2;
		return p->num;
	}
	cntCut++;

	return left < right? p->num + left : p->num + right;
}

int reorganize(int M, int K) {
	if(M*K < departments[1].employee) return 0;
	possible = 1;
	cntCut = 0;
	countCut(&departments[1], K);
	if(possible == 0) return 0;
	return (cntCut < M? 1 : 0);
}


---------------INPUT---------------
25 100
10
1 7 26
2 9 6 7 32
2 1 19 9 25
2 4 5 7 56
2 6 2 4 7
4 3 26 1
2 3 30 4 37
4 3 32 0
3 1 19
4 3 32 1
30
1 6932607 76
2 9335179 60 6932607 136
2 2930245 98 9335179 158
2 9212847 28 9335179 186
2 8207305 54 2930245 152
2 572001 54 2930245 206
2 3518315 8 8207305 62
2 2144677 10 9212847 38
2 2988431 28 572001 82
2 5269673 6 3518315 14
4 9 98 1
2 9199098 11 572001 93
4 10 97 0
3 572001 93
2 4206318 91 3518315 105
2 3101606 55 2144677 65
2 5690376 25 4206318 116
2 2263386 51 5269673 57
2 9579282 11 8207305 246
4 7 116 1
2 890815357 46 2263386 97
2 3290005 38 2144677 103
4 14 98 1
2 4109174 27 2263386 124
2 4494296 81 890815357 127
2 38935120 5 3290005 43
2 4077666 15 9579282 26
2 2768740 77 890815357 204
2 2048342 75 4077666 90
2 5076024 77 5690376 102
50
1 8500675 48
2 301711 80 8500675 128
2 64444969 46 301711 126
2 6923891 52 301711 178
2 19512429 46 64444969 92
2 1410967 32 64444969 124
2 9108591 64 1410967 96
2 616841 86 1410967 182
2 3430611 64 19512429 110
2 689679053 62 616841 148
4 5 148 1
2 3737550 31 3430611 95
2 1609584 53 616841 201
2 7054696 77 1609584 130
2 5900090 67 19512429 208
4 6 180 1
2 9148119 84 7054696 161
2 706908721 6 5900090 73
2 4766523 88 7054696 249
2 3391221 74 9148119 158
2 601626335 100 3391221 174
4 12 141 0
2 4606776 53 3737550 84
2 7380490 59 3391221 233
2 685557196 5 706908721 11
2 3024638 47 706908721 58
2 1213472 29 7380490 88
2 4561304 41 9108591 105
2 7312428 1 5900090 126
2 59782878 87 1213472 116
2 312064 45 9148119 478
2 9466386 35 685557196 40
4 17 130 1
2 5364047 20 7312428 21
4 19 126 1
2 771048 13 7380490 188
2 4375994 7 312064 52
2 5606524 57 685557196 97
2 9500590 47 1213472 163
3 3737550 84
2 5770171 28 59782878 115
2 9983507 4 9500590 51
2 491661 34 689679053 96
2 7391171 24 7312428 45
2 9064253 78 9500590 129
2 9785703 16 5770171 44
3 5770171 44
4 2 916 0
4 21 126 1
4 32 99 0
100
1 2409778 15
2 9077486 67 2409778 82
2 3019536 85 9077486 152
2 1837218 39 9077486 191
2 4795556 33 3019536 118
2 9088278 75 1837218 114
2 1920632 9 9088278 84
2 785196746 27 1920632 36
2 734568204 25 9088278 136
2 3600318 67 785196746 94
2 6766048 97 734568204 122
2 5476850 3 1920632 106
2 2182314 67 5476850 70
2 6148332 37 3019536 155
4 4 195 0
2 8202337 10 3600318 77
2 9035243 12 6766048 109
3 8202337 10
2 627284 73 6148332 110
3 9035243 12
4 12 97 1
2 2813864 53 3600318 120
2 5210272 29 2813864 82
2 9796658 95 2182314 162
2 408224308 89 5476850 254
3 2813864 82
4 9 121 1
4 3 338 0
2 4977619 92 6766048 189
2 2236621 30 408224308 119
2 287607 56 9796658 151
2 144463 96 627284 169
2 830923113 90 2236621 120
2 5392819 40 9796658 191
2 2992779 24 627284 193
2 638767 100 144463 196
2 1563465 70 785196746 164
4 9 200 1
2 2394522 83 1563465 153
2 9480530 43 734568204 257
2 9816532 9 408224308 218
4 18 134 1
2 8441385 22 5392819 62
2 5620723 56 5392819 118
2 3990893 34 1563465 187
2 4887831 32 3990893 66
2 1464605 42 638767 142
2 9203381 10 2182314 346
3 9796658 269
2 3361814 23 9816532 32
2 4545912 93 830923113 183
2 68810 71 3361814 94
2 4835714 63 68810 134
2 7860960 57 638767 199
3 1837218 1241
2 6902773 90 7860960 147
2 926792119 76 9077486 780
4 8 142 1
4 11 99 0
4 12 100 1
2 3435646 75 7860960 222
2 944672 33 6902773 123
2 416818 63 1464605 105
2 339520308 9 926792119 85
2 3106732 53 6902773 176
2 6224990 31 416818 94
4 3 419 1
3 9203381 -1
2 7197842 95 339520308 104
2 2661524 81 2992779 105
2 83432 5 944672 38
2 3069882 51 144463 696
2 8207730 55 339520308 159
2 6370932 89 3435646 164
4 13 146 0
2 8796489 2 4795556 35
2 285104223 24 2661524 105
4 11 164 1
2 9653518 75 1464605 211
2 7113036 45 83432 50
2 7586430 71 3069882 122
2 7130550 35 83432 85
2 4434328 49 6148332 1299
2 397635050 95 7197842 190
2 7180194 99 926792119 429
2 3635034 83 9653518 158
3 339520308 254
2 170152037 38 7180194 137
2 2259689 58 7586430 129
4 21 121 0
2 9636922 79 944672 197
3 4434328 49
3 4835714 -1
3 397635050 -1
2 3124785 74 7180194 211
2 3731 52 6370932 141
2 1758903 40 9653518 198
4 3 727 0
2 7768624 29 3069882 209
2 9330728 29 3731 81
200
1 437235 60
2 9929919 68 437235 128
2 7809753 26 9929919 94
2 4221859 32 9929919 126
2 8040861 62 7809753 88
2 8675253 74 7809753 162
2 7695775 56 8040861 118
2 1837241 82 8675253 156
2 9897859 44 8040861 162
2 272125 94 1837241 176
2 5901479 4 8675253 254
2 5067137 74 7695775 130
2 3233419 12 4221859 44
2 2474821 94 5901479 98
2 5449391 64 9897859 108
2 409576393 82 5901479 180
2 7547283 36 3233419 48
2 5139469 78 409576393 160
2 2141093 78 7547283 114
2 8938383 8 5139469 86
2 5536681 54 3233419 180
2 615141747 16 7547283 130
2 7732717 38 5067137 112
2 8619287 80 5536681 134
3 5449391 64
4 21 93 0
2 2584457 78 7732717 116
3 5536681 134
2 3181440 37 5139469 123
3 4221859 174
2 4502757 74 409576393 279
2 931052265 70 9929919 1143
3 2584457 78
2 6422842 59 931052265 129
2 9519100 45 7732717 83
4 12 130 1
2 7371951 64 7732717 147
2 2755039 100 931052265 229
3 4502757 74
2 2501688 89 409576393 294
2 5528714 71 8938383 79
2 9337036 69 2501688 158
2 5876606 83 9337036 152
2 8917152 81 2501688 322
2 9325874 3 5876606 86
2 886597008 13 8917152 94
2 56737502 15 8917152 109
3 9325874 3
2 5075641 38 7695775 315
2 3195857 90 7371951 154
4 30 99 0
2 783618 35 3181440 72
2 6840196 25 5528714 96
2 2095734 43 9519100 88
4 26 100 1
2 1594289 74 5075641 112
4 10 259 0
2 6700360 97 56737502 112
2 2219584 17 3195857 107
2 9343314 3 5876606 86
2 6752266 11 6840196 36
2 5624770 63 9337036 218
2 9008196 17 2095734 60
4 8 348 1
2 4842841 94 6700360 191
2 1870883 44 783618 79
2 753181 90 783618 169
3 5075641 112
2 74437796 25 7371951 196
2 1819542 59 74437796 84
2 9350904 77 9519100 182
2 7907462 11 9350904 88
2 98152 53 2095734 113
2 7328314 67 56737502 273
2 950309628 57 2755039 157
3 6700360 191
2 185647 20 9343314 23
2 573068873 98 950309628 155
2 2662035 36 5067137 649
3 185647 20
2 9403612 41 1870883 85
3 615141747 -1
2 3154193 46 2662035 82
2 9530395 80 7907462 91
2 7260351 20 1819542 79
2 257541593 10 74437796 114
2 8784931 84 9343314 87
2 2919069 66 6840196 102
4 55 99 0
3 2219584 17
2 2768205 10 5624770 73
2 1043191 96 1819542 175
2 2773969 26 6752266 37
2 3881435 100 2768205 110
4 35 128 1
3 2919069 66
2 4961547 28 9343314 115
4 20 198 1
2 2570612 21 6752266 58
2 8636002 3 9008196 20
3 6700360 -1
2 4674399 72 9350904 240
2 9305849 50 7907462 141
2 5268029 38 8784931 122
2 406101 14 9008196 34
2 8221549 6 98152 59
4 61 100 1
2 9848302 35 950309628 190
2 5243046 91 2570612 112
2 923358 27 573068873 125
2 4706204 89 8784931 211
2 7956814 51 5243046 142
4 52 100 1
2 9289179 36 4961547 64
4 25 192 1
2 6434234 19 7328314 86
2 6743142 27 886597008 40
2 6012190 51 4674399 123
2 2398678 75 1870883 160
2 8241464 93 5268029 131
2 4572938 99 8241464 192
2 6501580 1 3195857 91
2 1911236 49 2570612 212
2 656188 53 2773969 79
2 2945902 23 6422842 82
4 66 100 1
4 33 161 0
2 9658504 85 4572938 184
2 659290 35 8221549 41
2 963264274 79 6012190 130
2 3631380 9 4674399 211
2 396556684 49 6840196 376
3 74437796 210
2 4306433 10 98152 104
2 1851147 76 5268029 391
2 3235397 10 9403612 51
2 6470703 64 9305849 114
2 3810121 82 8241464 359
2 3578207 40 5624770 213
2 339199993 38 9403612 89
2 8151619 92 7328314 178
2 3516093 82 8636002 85
4 15 375 0
2 9031222 59 7956814 110
2 7952408 33 9848302 68
2 5588780 21 4706204 110
3 5588780 21
2 1513505 70 6470703 134
2 1851563 56 8636002 141
2 1886595 28 3235397 38
2 5096539 96 8151619 188
4 12 510 0
2 4376964 53 3516093 135
4 64 113 0
2 6309847 32 9305849 216
2 2872541 82 3516093 217
2 639751 16 656188 69
2 198241 86 9658504 171
2 1655531 8 56737502 297
2 8988837 58 3235397 96
2 2274365 94 2398678 169
4 41 175 1
3 3631380 9
2 54081 66 7952408 99
3 5588780 -1
2 362162 3 1886595 31
2 3537716 65 339199993 103
2 4115622 35 7956814 145
4 28 259 0
2 626209 86 9658504 257
2 3844281 90 8221549 131
3 8221549 131
2 598928458 59 7952408 158
2 5097228 17 54081 83
3 4572938 356
2 877441 38 1655531 46
2 2664023 20 3810121 102
2 7706545 42 272125 136
3 6012190 130
4 76 100 1
2 9600501 74 2664023 94
4 29 239 0
2 393686 19 2768205 129
2 7394062 15 923358 42
4 34 209 0
2 1540265 90 4306433 100
4 97 100 1
2 418402682 67 9848302 277
2 6203570 75 3881435 175
2 4342068 57 1886595 88
4 84 99 0
2 7560329 82 9289179 118
3 4502757 -1
2 8281434 43 6309847 75
4 104 100 1
2 7815031 72 6434234 91
2 5525329 14 1851563 70
2 9056859 36 2398678 205
2 6721921 90 406101 104
3 5096539 96