Untitled
plain_text
a month ago
13 kB
7
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