QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#317193#6692. Building CompanysqzAC ✓96ms25088kbC++142.0kb2024-01-28 17:37:592024-01-28 17:38:00

Judging History

你现在查看的是最新测评结果

  • [2024-01-28 17:38:00]
  • 评测
  • 测评结果:AC
  • 用时:96ms
  • 内存:25088kb
  • [2024-01-28 17:37:59]
  • 提交

answer

#include <bits/stdc++.h>
#define MAXN ((int) 1e5)
using namespace std;
typedef pair<int, int> pii;

int g, n, A[MAXN + 10][2];

// M[i] 表示第 i 项工程还有几条要求未满足
int M[MAXN + 10];
// B[i] 表示第 i 项工程的奖励
vector<pii> B[MAXN + 10];

// mp[i] 是一个按人数排序的小根堆,维护了与工种 i 有关的未满足需求
unordered_map<int, priority_queue<pii, vector<pii>, greater<pii>>> mp;
// have[i] 表示公司现有工种 i 的员工数量
unordered_map<int, long long> have;
queue<int> q;

// 公司增加工种 t 的员工共 u 名
void add(int t, int u) {
    long long &val = have[t];
    val += u;
    priority_queue<pii, vector<pii>, greater<pii>> &pq = mp[t];
    // 看哪些和工种 t 有关的需求被满足了
    while (!pq.empty()) {
        pii p = pq.top();
        if (p.first > val) break;
        pq.pop();
        // 工程所有要求都被满足,加入队列
        if ((--M[p.second]) == 0) q.push(p.second);
    }
}

int main() {
    scanf("%d", &g); assert(g >= 1);
    for (int i = 1; i <= g; i++) scanf("%d%d", &A[i][0], &A[i][1]);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &M[i]);
        for (int j = 1; j <= M[i]; j++) {
            int a, b; scanf("%d%d", &a, &b);
            mp[a].push(pii(b, i));
        }
        int K; scanf("%d", &K);
        for (int j = 1; j <= K; j++) {
            int c, d; scanf("%d%d", &c, &d);
            B[i].push_back(pii(c, d));
        }
    }

    // 把没有任何要求的工程加入队列
    for (int i = 1; i <= n; i++) if (M[i] == 0) q.push(i);
    // 公司一开始就有的员工
    for (int i = 1; i <= g; i++) add(A[i][0], A[i][1]);

    int ans = 0;
    // 类似拓扑排序,不断从队列中拿出工程,并获得奖励
    while (!q.empty()) {
        int idx = q.front(); q.pop();
        ans++;
        for (pii p : B[idx]) add(p.first, p.second);
    }
    printf("%d\n", ans);
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 7136kb

input:

2 2 1 1 2
5
1 3 1
0
2 1 1 2 1
2 3 2 2 1
3 1 5 2 3 3 4
1 2 5
3 2 1 1 1 3 4
1 1 3
0
1 3 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 6356kb

input:

3 610031727 590328742 816793299 18485566 654221125 47823436
10
3 610031727 224714165 816793299 491951703 654221125 593479446
1 610031727 538596643
1 610031727 551036304
3 816793299 262985484 610031727 52580932 654221125 424397787
1 654221125 889197190
3 654221125 126924193 610031727 963399336 816793...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 1ms
memory: 6140kb

input:

10 720543365 814021419 777649737 273919247 339754140 472967790 545693058 298289557 949226024 176807538 267294560 819212220 337794335 504610276 137418995 614590802 632556957 783062334 587607535 115519693
100
5 949226024 327424834 777649737 117746775 137418995 152960310 720543365 423301366 267294560 4...

output:

100

result:

ok 1 number(s): "100"

Test #4:

score: 0
Accepted
time: 2ms
memory: 6524kb

input:

33 598906111 952747266 214206082 308472115 773699301 71970369 334282917 266176016 861160505 745480638 397625705 130382274 75028923 106125916 739923352 754152044 493886549 212094717 352869179 727757279 697376464 343501623 916521518 80952344 90959088 722016125 286878647 329186592 770901193 30277256 92...

output:

100

result:

ok 1 number(s): "100"

Test #5:

score: 0
Accepted
time: 39ms
memory: 8768kb

input:

380 562284409 583959039 705240193 694592025 91058796 151967354 775570098 571811699 457579493 117213529 684664737 33837962 60865228 186423701 316573783 868301583 744570505 934432338 790259030 364551324 145817136 961903964 737096543 759008968 865899868 681823261 273067044 247683791 186025557 756452454...

output:

992

result:

ok 1 number(s): "992"

Test #6:

score: 0
Accepted
time: 51ms
memory: 8776kb

input:

3 293768553 273246573 143991316 507392430 358993111 920969223
100000
4 46041344 835899600 358993111 994240598 293768553 484011013 143991316 777828426
0
0
0
5 143991316 794586365 46041344 405796774 722229657 508855404 293768553 369514799 358993111 4028509
3 143991316 258883273 358993111 986311988 460...

output:

100000

result:

ok 1 number(s): "100000"

Test #7:

score: 0
Accepted
time: 46ms
memory: 9120kb

input:

2 961288235 443865989 396580494 578798612
100000
34 421946957 299618245 78391742 196256544 561711742 14201606 657355823 12773731 46715022 916005233 307668801 286702191 158073396 813604706 961288235 632264049 137129358 649927330 69336461 331852084 768586802 142594294 800292046 696090805 674814060 644...

output:

100000

result:

ok 1 number(s): "100000"

Test #8:

score: 0
Accepted
time: 31ms
memory: 10168kb

input:

118 302362725 748141404 107046714 926152648 886186708 125758872 452810643 243408822 807034444 7712734 770559271 84899208 578273022 102765302 276241387 922873983 952906448 582532305 67022370 663519345 379715473 619080027 481503038 207664807 267966322 105276315 179029836 537064295 838588147 386785169 ...

output:

99787

result:

ok 1 number(s): "99787"

Test #9:

score: 0
Accepted
time: 49ms
memory: 9540kb

input:

4016 425997364 663530985 32966549 596915680 137587205 104946426 298723053 599259382 939060651 757103513 834187743 991771357 184236672 862128650 635325377 297946798 232842933 209468554 643350488 250802223 626586838 254169793 129332987 565726855 177102769 688787830 215857 981092561 405189873 823755261...

output:

99986

result:

ok 1 number(s): "99986"

Test #10:

score: 0
Accepted
time: 59ms
memory: 14180kb

input:

35044 48622731 251212400 732521804 902344317 273291991 81327394 811715101 704212871 319685093 307618853 60847749 119531511 61204726 872447051 718526247 184449546 114803695 615724654 807305507 137996462 272886020 101753654 526032252 511153835 911672776 613553528 126969597 247768227 663303181 10917585...

output:

99989

result:

ok 1 number(s): "99989"

Test #11:

score: 0
Accepted
time: 70ms
memory: 19504kb

input:

32907 121165330 843174578 416133175 990685470 648969197 965850907 277624455 475372239 706722409 818172286 796783959 780404920 767409027 796679811 750255196 494079037 199763846 497603568 594904540 575743410 112353565 95634554 12710847 545357746 65924711 111218563 197800795 490255222 816174218 4078180...

output:

99989

result:

ok 1 number(s): "99989"

Test #12:

score: 0
Accepted
time: 92ms
memory: 21436kb

input:

94529 522696088 835790500 648724392 720614924 910281587 519838536 84910923 731990712 61591898 162418925 209336449 108997388 716923265 995969268 47023140 520861794 683421649 603985476 248519461 866417569 124127917 574795147 65376310 835435760 875938023 145399939 423036596 784142347 807073179 47241566...

output:

99983

result:

ok 1 number(s): "99983"

Test #13:

score: 0
Accepted
time: 96ms
memory: 20908kb

input:

85314 513819850 718028847 365712067 546433969 635098004 712238377 60502917 383502059 253501940 532281679 967285121 391066393 111919427 400028969 760490348 364973517 779747450 466771425 440572357 920270327 319750012 589620880 210468477 156377127 518651618 355806565 522755701 776107532 18184823 434915...

output:

99988

result:

ok 1 number(s): "99988"

Test #14:

score: 0
Accepted
time: 35ms
memory: 25088kb

input:

1 1000000000 602102863
100000
1 99996 635961043
1 99997 428581297
1 99995 517042686
1 99996 635961043
1 99994 930742857
1 99995 517042686
1 99993 511459974
1 99994 930742857
1 99992 548233271
1 99993 511459974
1 99991 310676710
1 99992 548233271
1 99990 438997140
1 99991 310676710
1 99989 406491162
...

output:

99997

result:

ok 1 number(s): "99997"

Test #15:

score: 0
Accepted
time: 42ms
memory: 24276kb

input:

1 1000000000 880684411
100000
1 99996 511847416
1 99997 22361850
1 99995 351167748
1 99996 511847416
1 99994 770188930
1 99995 351167748
1 99993 536199253
1 99994 770188930
1 99992 596449963
1 99993 536199253
1 99991 941676274
1 99992 596449963
1 99990 426334027
1 99991 941676274
1 99989 785784305
1...

output:

99997

result:

ok 1 number(s): "99997"

Test #16:

score: 0
Accepted
time: 51ms
memory: 24452kb

input:

1 1000000000 603976360
100000
1 99996 537476894
1 99997 616142404
1 99995 330517001
1 99996 537476894
1 99994 164924602
1 99995 330517001
1 99993 116228132
1 99994 164924602
1 99992 234601247
1 99993 116228132
1 99991 162610429
1 99992 234601247
1 99990 3605505
1 99991 162610429
1 99989 460044745
1 ...

output:

99997

result:

ok 1 number(s): "99997"