Untitled
unknownplain_text
a month ago
13 kB
10
Indexable
Never
--------------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;
}
--------------USER------------------
#define MAX_NODE 18001
#define HASH_SIZE 36001
using namespace std;
struct Node {
int mId;
Node* parent;
Node* child[3];
int num;
int hashNext;
bool valid;
Node(){
parent = nullptr;
for(int i = 0; i < 3; i++) child[i] = nullptr;
num = 0;
hashNext = -1;
valid = false;
}
bool addChild(Node* n){
for(int i = 0; i < 3; i++){
if(child[i] == nullptr){
child[i] = n;
return true;
}
}
return false;
}
void removeChild(Node* n){
for(int i = 0; i < 3; i++){
if(child[i] == n){
child[i] = nullptr;
}
}
}
}departments[MAX_NODE];
int departmentCnt, groupCnt;
int hashTb[HASH_SIZE];
void addHash(int id)
{
int h = departments[id].mId % HASH_SIZE;
departments[id].hashNext = hashTb[h];
hashTb[h] = id;
}
int getHash(int mId)
{
int h = mId % HASH_SIZE;
int id = hashTb[h];
while(id != -1 && departments[id].mId != mId){
id = departments[id].hashNext;
}
return id;
}
void init(int N, int mId[], int mNum[]) {
departmentCnt = 0;
for(int i = 0; i < HASH_SIZE; i++){
hashTb[i] = -1;
}
for(int i = 0; i < MAX_NODE; i++){
departments[i] = Node();
}
groupCnt = N;
for (int i = 0; i < N; ++i) {
Node* node = &departments[departmentCnt];
node->valid = true;
node->num = mNum[i];
node->mId = mId[i];
addHash(departmentCnt);
departmentCnt++;
}
}
int add(int mId, int mNum, int mParent) {
int idParent = getHash(mParent);
Node* node = &departments[departmentCnt];
Node* parent = &departments[idParent];
if(!parent->addChild(node))
return -1;
Node* curr = parent;
while (curr) {
curr->num += mNum;
curr = curr->parent;
}
node->mId = mId;
node->valid = true;
node->parent = parent;
node->num = mNum;
addHash(departmentCnt);
departmentCnt++;
return parent->num;
}
int remove(int mId) {
int idx = getHash(mId);
if(idx == -1) return -1;
Node* node = &departments[idx];
if (!node || !node->valid) {
return -1;
}
Node* parent = node->parent;
Node* curr = parent;
while (curr) {
if (!curr->valid){
node->valid = false;
return -1;
}
curr->num -= node->num;
curr = curr->parent;
}
node->valid = false;
parent->removeChild(node);
return node->num;
}
int distribute(int K) {
int low = 1, high = 0;
for (int i = 0; i < groupCnt; ++i) {
if (departments[i].num > high)
high = departments[i].num;
}
while (low <= high) {
int mid = (low + high) / 2;
int sum = 0;
for (int i = 0; i < groupCnt; ++i) {
if (departments[i].num <= mid)
sum += departments[i].num;
else
sum += mid;
}
if (sum <= K) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return high;
}
--------------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
50
1 5
842745 82
5076024 77
8500675 48
5835274 11
8640445 62
2 4506471 64 8500675 112
2 7470401 90 5076024 167
2 8674635 60 5835274 71
4 490 163
2 2898467 44 8640445 106
2 2670877 70 7470401 160
2 2987079 36 4506471 100
2 3136289 14 5076024 251
2 4331691 56 2987079 92
2 9033317 50 3136289 64
2 5585359 84 9033317 134
2 7877097 10 4331691 66
2 2307507 68 4331691 134
2 958168877 30 5585359 114
2 9148119 84 9033317 248
2 706908721 6 4331691 140
2 4766523 88 2307507 156
2 3391221 74 5585359 188
2 601626335 100 9033317 422
4 1138 503
2 8648247 76 3391221 150
2 2536849 90 601626335 190
2 2727195 96 4331691 -1
2 5728981 38 601626335 228
2 4452159 72 8674635 132
2 1151321 2 706908721 8
2 7337251 92 2536849 182
4 1460 751
2 5553147 28 3391221 178
2 1452597 78 958168877 108
3 2536849 182
2 7346966 95 9148119 179
2 6891000 61 5553147 89
2 9865290 47 4766523 135
2 407564 17 6891000 78
2 2674110 39 4766523 174
2 5573344 37 5553147 143
2 4820824 61 9865290 108
4 1842 986
3 4452159 72
2 5770171 28 2898467 72
2 3991925 22 6891000 100
2 7363039 8 5835274 79
2 2772089 14 1452597 92
2 7391171 24 8640445 158
2 9064253 78 6891000 178
2 9785703 16 1452597 108
3 6891000 178
4 1672 828
100
1 10
364095 24
9369398 71
9703257 78
7834648 53
8930467 36
2908778 59
1373085 86
7485100 61
6813639 32
9353566 63
2 1317632 49 9353566 112
2 4324882 63 6813639 95
2 8923924 93 4324882 156
2 4541446 95 8923924 188
2 989800 45 9369398 116
2 4681914 27 1317632 76
2 3799292 65 4541446 160
2 7581102 59 6813639 407
4 932 280
2 2561766 67 1317632 143
2 1206856 69 1317632 212
4 980 233
2 6181056 97 1206856 166
2 2477394 91 4324882 407
2 627284 73 2477394 164
3 1206856 166
4 1278 559
2 558147431 64 2477394 228
2 2210369 82 989800 127
2 713547 4 3799292 69
2 3016965 2 2561766 69
4 1342 539
4 1197 394
4 1342 539
4 1197 394
2 3700021 6 2210369 88
2 7853983 76 989800 209
2 5532601 74 7485100 135
2 8548355 60 4681914 87
3 7581102 59
4 1536 517
2 7898344 5 1317632 210
2 2989754 39 713547 43
3 2477394 228
3 2210369 88
2 9835636 85 5532601 159
2 2548204 65 2989754 104
2 2394522 83 3016965 85
2 3924828 9 1373085 95
2 9595150 31 5532601 190
2 6452016 65 8548355 125
2 6441922 71 9835636 156
2 3839556 65 713547 173
4 1477 313
2 4905916 45 9835636 201
2 390382 11 6452016 76
4 1560 341
2 3746342 31 8548355 167
4 1586 349
2 9564510 83 9353566 546
2 1624064 73 9835636 274
2 4545912 93 3924828 102
2 5681520 5 7853983 81
2 4835714 63 2394522 146
2 3063556 41 5532601 420
2 3090678 19 2548204 84
2 1831640 17 3799292 274
2 6495312 1 3746342 32
3 2477394 -1
2 6902773 90 7898344 95
2 4503903 96 7898344 191
2 4588409 98 4835714 161
2 786676547 96 6495312 97
2 2038333 18 4545912 111
2 4937959 72 2548204 156
2 905537 6 4905916 51
2 4823627 24 6495312 121
4 2310 585
2 5238691 8 4905916 59
2 7754141 70 3839556 135
2 7697735 24 4588409 122
2 25614881 50 3090678 69
3 9564510 83
2 7197842 95 905537 101
2 2661524 81 6902773 171
2 8245510 75 3090678 144
2 83432 5 9703257 83
2 3069882 51 4823627 75
2 2814204 1 4905916 155
2 6370932 89 8930467 125
4 2665 663
3 4905916 155
2 2900615 64 2394522 332
4 2748 782
3 786676547 96
4 3001 994
2 147932 77 6902773 248
2 9653518 75 6495312 151
2 7026352 1 6902773 249
2 9217602 91 1624064 164
2 8128452 1 7754141 71
2 7130550 35 8128452 36
2 4434328 49 25614881 99
2 397635050 95 8548355 413
2 314175752 13 2548204 343
2 3635034 83 4545912 194
3 83432 5
2 9635319 96 9653518 171
2 7918033 2 9653518 173
200
1 20
7411184 33
237531 20
9321858 95
9851157 70
124082308 13
7105279 80
5592310 87
5292953 82
8115416 53
2361827 40
5554474 51
9647197 98
3023340 77
1054599 8
625998366 31
4425313 2
5964864 25
9305579 80
5232978 3
2310693 26
2 4702735 24 5964864 49
2 6239657 58 9647197 156
2 437235 60 237531 80
2 6740461 78 625998366 109
2 7451927 88 5292953 170
2 5055729 78 437235 138
4 1265 129
2 6637577 38 5055729 116
2 8096339 28 2310693 54
2 5625037 58 9305579 138
2 7646967 60 4702735 84
2 8343249 18 5554474 69
2 624842843 40 7451927 128
2 5023125 46 437235 222
2 9126911 8 5964864 117
2 6758169 94 624842843 134
2 981212259 64 9851157 134
3 8343249 18
2 1328492 93 6239657 151
3 1328492 93
2 6536545 26 4425313 28
2 3056761 86 437235 308
2 5581073 90 6637577 128
3 1328492 -1
2 5929154 31 624842843 165
2 4318916 45 3056761 131
2 5405238 51 7451927 304
2 1056280 81 3056761 212
4 1809 266
4 2030 377
4 1986 355
3 5055729 206
2 4713287 60 2361827 100
2 6920097 18 9851157 152
3 8343249 -1
3 6740461 78
2 4631939 52 5625037 110
2 1662717 26 9647197 182
2 9847079 56 5023125 102
2 267465985 42 9851157 194
2 541765145 90 8096339 118
2 8262627 32 9847079 88
2 4032861 70 6758169 164
3 5405238 51
3 6536545 26
2 3428577 14 5625037 124
2 7399417 74 9847079 162
2 304195 52 9847079 214
2 8436123 36 1054599 44
2 595669 6 5292953 411
3 6758169 164
2 1213500 65 624842843 136
2 8199534 15 5232978 18
2 886597008 13 624842843 149
2 9715490 43 5625037 167
2 1651418 67 9126911 75
2 1797138 43 267465985 85
4 2147 238
3 8262627 32
2 1763965 38 4631939 90
2 5744935 8 5929154 39
4 2441 392
2 5853439 88 5744935 96
2 8946647 44 541765145 134
2 1594289 74 3056761 286
4 2470 355
4 2748 567
2 2862197 10 1651418 77
2 1348063 84 1662717 110
2 7371129 14 2862197 24
2 8196291 68 5929154 195
4 2804 468
2 8138139 60 7105279 140
2 2024021 94 7399417 168
2 36896191 16 4318916 61
2 4842841 94 8436123 130
2 1870883 44 7399417 212
2 3032187 60 541765145 194
2 4648117 38 1056280 119
4 2854 386
2 5720013 42 7399417 254
2 5042551 4 1763965 42
2 6433489 94 5929154 289
2 6328411 68 8946647 112
2 9903253 54 3032187 114
2 7530367 24 5720013 66
2 24857 86 8436123 216
2 8390883 76 9847079 462
3 5853439 88
2 562213100 73 24857 159
4 3715 853
2 980836 81 6920097 99
3 4318916 61
4 3468 525
2 5046711 16 5964864 224
2 3154193 46 6433489 140
2 9530395 80 5046711 96
2 3191253 26 886597008 39
2 7260351 20 8946647 132
2 257541593 10 9126911 109
2 8784931 84 3056761 363
2 2919069 66 1651418 157
4 4034 827
2 3000117 18 8138139 78
2 6992031 60 304195 112
2 1043191 96 541765145 432
2 2773969 26 5720013 92
2 3881435 100 4842841 194
4 4414 993
2 7909939 32 8138139 110
2 1263405 30 8946647 162
2 8438103 20 5042551 24
4 3769 449
2 831581 42 1056280 161
2 2135303 84 3032187 198
2 7036897 2 3881435 102
4 4155 583
2 9305849 50 1263405 80
2 2093457 54 3000117 72
2 6744347 52 6328411 120
2 406101 14 24857 173
2 799807 28 8196291 96
2 967329113 46 1797138 89
2 8873635 76 1797138 165
2 2047389 46 8784931 130
4 4883 974
2 418347829 58 8196291 154
2 580689439 32 6328411 152
2 6844089 46 1054599 459
2 4248451 92 8115416 145
2 517288189 50 5046711 146
3 8873635 76
2 8815294 39 6844089 85
2 2061536 97 5744935 105
2 1998962 3 2093457 57
2 9020916 69 9321858 164
3 3428577 14
2 4705865 90 3154193 136
2 9750497 38 7260351 58
2 5111801 94 831581 136
2 9687619 40 1043191 136
2 1197501 26 8138139 193
2 3807335 36 2093457 93
2 5091649 34 1662717 144
2 2417753 74 1662717 218
2 7493923 100 4842841 296
2 847739 4 5042551 28
2 1967285 66 8815294 105
2 6895135 8 9903253 62
4 5255 698
2 1714679 56 4648117 94
2 9933009 66 9750497 104
4 5978 1091
2 2758249 78 7260351 202
2 6189235 60 562213100 133
2 1851147 76 580689439 108
2 3235397 10 7371129 24
2 6470703 64 5720013 156
2 3810121 82 1197501 108
2 1318547 20 5046711 166
2 5423851 100 2024021 194
4 5522 729
2 8151619 92 1851147 168
2 3516093 82 6470703 146
4 6076 951
3 6470703 146
2 7559620 73 1998962 76
3 2135303 84
2 8438105 22 9305849 72
2 2723 36 580689439 236
2 6295453 62 831581 198
2 5098311 16 967329113 62
2 1513505 70 406101 84
2 1851563 56 1043191 192
2 1886595 28 2919069 94
2 4438013 86 6189235 146
2 9779879 24 2758249 102
2 6551553 94 1318547 114
3 1851563 56
2 8134514 47 1513505 117
2 7796 85 8390883 161
2 8804582 59 4713287 119
2 7327816 49 2361827 208
2 648986 55 6992031 115
2 1410908 69 3000117 253
2 6799758 75 8151619 167
2 6052294 95 625998366 126
3 2758249 102
2 9192947 16 9903253 78
3 6744347 52
2 824965820 65 1886595 93
2 7249262 63 5592310 150
2 2556944 17 6799758 92
2 4065186 23 2773969 49
2 2047268 9 3810121 91
3 6470703 -1
2 3844281 90 8815294 195
3 4842841 296
2 598928458 59 3807335 95