QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#686803#4938. Writing TasksSanguineChameleon#WA 89ms42112kbC++202.3kb2024-10-29 15:46:442024-10-29 15:46:45

Judging History

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

  • [2024-10-29 15:46:45]
  • 评测
  • 测评结果：WA
  • 用时：89ms
  • 内存：42112kb
查看
  • [2024-10-29 15:46:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#define mp make_pair
#define eb emplace_back
#define pb push_back
typedef pair<int,int> pii;




const int mxn=1e6+5;

vector<int> adjl[mxn];
bool vis[mxn];
bool col[mxn];
int b,w;
void dfs(int nd,int cc=0){
    col[nd]=cc;
    if(col[nd])b++;
    else w++;
    vis[nd]=1;
    for(int x:adjl[nd]){
        if(vis[x]){
            //assert(col[x]!=col[nd]);
            continue;
        }
        dfs(x,1-cc);
    }
}


vector<pii> tt[mxn],cc[mxn];//each topic/contest, authors they're connected to
vector<pair<int,pii> > trips;
vector<int> nodes[mxn];
int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int a,c,t;
    cin>>a>>c>>t;
    int cur=1;
    for(int i=1;i<=a;i++){
        int l;cin>>l;
        for(int j=0;j<l;j++){
            int a;cin>>a;
            //author i -> contest a
            cc[a].eb(i,cur++);
        }
    }

    for(int i=1;i<=a;i++){
        int l;cin>>l;
        for(int j=0;j<l;j++){
            int a;cin>>a;
            //author i -> topic a
            tt[a].eb(i,cur++);
        }
    }

    int xx=1;
    for(int i=1;i<=c;i++){
        int l;cin>>l;
        for(int j=0;j<l;j++){
            int a;cin>>a;
            //cur: contest i -> topic a
            for(pii x:cc[i]){
                for(pii y:tt[a]){
                    if(x.f==y.f){
                        //triangle: author, contest, topic
                        nodes[x.s].pb(trips.size());
                        nodes[y.s].pb(trips.size());
                        nodes[cur].pb(trips.size());
                        trips.eb(x.f,mp(i,a));
                    }
                }
            }
            cur++;
        }
    }

    // for(auto x:trips){
    //     cout<<x.f<<' '<<x.s.f<<' '<<x.s.s<<'\n';
    // }

    for(int i=1;i<cur;i++){
        assert(nodes[i].size()<=2);
        if(nodes[i].size()==2){
            int u=nodes[i][0];
            int v=nodes[i][1];
            adjl[u].pb(v);
            adjl[v].pb(u);
            // cout<<u<<' '<<v<<'\n';
        }
    }

    int ans=0;
    for(int i=0;i<trips.size();i++){
        if(vis[i])continue;
        b=w=0;
        dfs(i);
        if(b<w)swap(b,w);
        ans+=b;
    }
    cout<<ans;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 5648kb

input:

2 3 2
2 1 2
2 2 3
1 1
1 1
1 1
1 1
1 2

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 4ms
memory: 3592kb

input:

2 2 2
0
1 2
0
2 1 2
2 1 2
0

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 65ms
memory: 38792kb

input:

40623 39265 42226
2 14643 37432
2 29610 20181
2 6441 7614
2 17559 3238
2 39001 17644
2 6431 37097
2 6347 12246
2 1130 1688
2 38583 9078
2 8746 27832
2 13090 39048
2 32647 18777
2 27505 19277
2 31201 25824
2 6133 20344
2 11625 20997
2 18528 35730
0
2 22986 5273
2 10942 38791
2 19025 35679
2 32321 124...

output:

78528

result:

ok single line: '78528'

Test #4:

score: 0
Accepted
time: 84ms
memory: 41632kb

input:

41022 39421 42288
2 26413 2168
2 24182 14199
2 18798 17846
2 3398 19624
2 16796 33998
2 7209 25883
2 26356 13537
2 56 30294
2 34909 20218
2 29727 22116
2 16349 1704
2 9254 18036
2 16197 16096
2 21562 31470
2 14773 10518
2 38025 12573
2 15509 32276
2 9613 12321
2 19146 11395
2 7186 36431
0
2 10098 22...

output:

78840

result:

ok single line: '78840'

Test #5:

score: 0
Accepted
time: 89ms
memory: 42112kb

input:

49395 43808 45888
2 13031 11323
2 41375 4393
2 32137 17908
2 29053 42691
0
2 38335 30970
2 38318 43773
2 22999 22444
0
2 39248 30837
0
2 29807 2360
2 29363 3536
2 8515 41137
2 7890 31441
0
2 31070 6987
2 24295 15517
2 14204 13069
2 32996 40146
2 38164 1478
2 40032 19143
0
2 18430 24119
2 37845 33290...

output:

87616

result:

ok single line: '87616'

Test #6:

score: 0
Accepted
time: 4ms
memory: 3656kb

input:

3 4 3
1 2
2 4 2
2 1 3
1 1
2 2 3
2 3 2
1 3
2 1 3
1 2
1 2

output:

5

result:

ok single line: '5'

Test #7:

score: 0
Accepted
time: 4ms
memory: 5780kb

input:

15 17 18
1 12
2 13 4
2 2 6
2 11 14
2 7 3
2 17 11
2 4 8
2 5 1
1 1
1 16
1 3
2 10 16
1 8
2 15 5
1 6
2 6 1
2 7 3
1 13
2 12 9
2 8 18
1 9
2 1 15
2 5 13
2 18 14
2 15 7
1 4
2 10 2
1 2
1 17
2 14 17
1 18
1 13
1 4
1 1
1 5
2 14 3
2 8 16
2 2 16
1 10
1 10
2 12 14
1 6
2 7 15
2 6 3
2 17 12
1 15
1 9

output:

15

result:

ok single line: '15'

Test #8:

score: 0
Accepted
time: 5ms
memory: 6012kb

input:

769 869 792
1 254
2 210 794
1 863
2 40 403
2 279 773
2 54 328
2 196 473
1 804
1 261
1 174
1 219
1 22
1 429
1 195
2 769 100
1 33
1 457
1 604
2 473 714
2 423 227
2 453 654
1 864
2 220 243
2 520 321
2 421 805
2 721 11
2 216 793
1 360
1 169
2 121 613
2 714 594
1 692
2 642 607
2 538 781
2 800 387
2 494 5...

output:

769

result:

ok single line: '769'

Test #9:

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

input:

46352 41211 38602
2 11300 5679
2 2876 4114
2 28525 6628
1 23785
1 30940
1 26982
1 8056
1 13748
2 25254 21974
1 3446
2 2294 13453
0
1 16724
2 36970 18406
2 7688 17413
1 25901
1 39238
1 16098
1 29911
2 15113 849
1 31293
2 32195 13287
0
1 12670
2 40732 19567
2 24195 23787
1 40913
2 18820 10009
0
0
2 23...

output:

38602

result:

ok single line: '38602'

Test #10:

score: 0
Accepted
time: 4ms
memory: 3728kb

input:

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

output:

3

result:

ok single line: '3'

Test #11:

score: 0
Accepted
time: 4ms
memory: 5712kb

input:

15 15 20
2 12 14
2 1 3
1 11
2 5 13
2 8 9
1 13
1 9
2 15 11
2 3 6
2 6 7
1 10
1 2
2 7 12
1 14
1 4
1 3
1 1
2 12 20
2 18 2
2 10 15
2 2 10
2 15 18
2 17 3
2 6 7
2 16 17
1 19
2 13 6
1 14
2 4 11
2 8 16
2 1 4
1 13
2 6 1
1 8
1 18
2 16 7
1 14
2 10 11
2 15 19
2 19 18
1 12
1 3
1 2
2 4 16
2 17 15

output:

16

result:

ok single line: '16'

Test #12:

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

input:

942 753 814
2 429 543
1 228
1 442
0
0
2 215 635
1 199
2 735 727
1 335
2 56 209
2 668 570
2 748 190
2 719 571
0
1 650
1 468
1 646
2 150 547
2 551 53
0
1 203
0
2 544 664
1 100
2 388 321
1 94
1 77
2 535 253
1 306
0
2 753 342
2 690 529
2 204 712
2 621 693
1 253
1 549
2 712 639
2 43 323
2 206 585
2 82 45...

output:

753

result:

ok single line: '753'

Test #13:

score: 0
Accepted
time: 4ms
memory: 5768kb

input:

15 20 16
2 8 7
2 7 13
2 11 20
2 4 9
2 18 6
2 10 13
2 11 5
2 10 3
2 8 1
2 12 5
2 9 2
2 17 3
2 20 1
2 17 18
2 16 19
2 4 12
2 7 6
2 11 13
2 8 3
2 7 3
2 11 14
1 9
2 5 2
2 6 13
2 15 1
2 14 1
2 15 2
2 9 10
2 12 5
2 8 4
2 9 8
2 9 6
2 7 16
2 14 10
2 10 8
2 1 13
1 15
1 16
2 11 5
2 11 12
2 14 3
0
2 4 13
2 7 1...

output:

5

result:

ok single line: '5'

Test #14:

score: 0
Accepted
time: 38ms
memory: 19940kb

input:

48398 47836 40164
2 18023 23816
0
0
1 14256
1 47537
2 40419 28208
2 24335 20756
2 11563 31099
2 11298 27901
1 43928
1 4795
2 33599 41395
1 40893
2 24858 20153
1 16524
2 73 9844
2 18804 12559
1 47263
1 36093
2 19492 7210
2 10991 38704
2 44074 26169
1 9493
2 23707 40251
1 19203
2 14974 45727
1 15661
2...

output:

40164

result:

ok single line: '40164'

Test #15:

score: 0
Accepted
time: 4ms
memory: 5648kb

input:

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

output:

4

result:

ok single line: '4'

Test #16:

score: 0
Accepted
time: 4ms
memory: 3608kb

input:

19 20 20
1 16
2 10 7
1 13
2 11 2
1 8
1 7
2 20 17
2 5 13
1 2
2 6 8
2 3 15
2 9 5
1 4
1 18
2 19 1
2 12 1
2 14 19
2 17 11
1 15
1 8
1 10
1 13
2 17 1
2 20 4
2 16 6
2 4 9
1 14
1 5
1 7
1 18
1 15
1 1
2 6 11
2 2 16
2 9 14
2 3 17
1 19
1 12
0
1 5
1 18
2 1 8
2 14 12
2 7 2
1 16
2 20 5
2 15 11
2 10 13
2 17 1
2 9 4...

output:

19

result:

ok single line: '19'

Test #17:

score: 0
Accepted
time: 4ms
memory: 3960kb

input:

858 936 831
1 78
2 132 126
0
2 761 378
1 914
1 36
2 884 480
2 344 531
2 718 395
2 30 270
2 503 495
2 717 520
1 833
2 483 636
1 498
2 181 250
2 538 311
0
2 246 552
1 201
2 598 595
2 672 747
2 823 508
2 429 369
1 705
2 929 659
1 866
2 423 31
2 425 921
2 422 313
2 927 726
1 194
2 553 919
2 733 323
1 12...

output:

831

result:

ok single line: '831'

Test #18:

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

input:

49781 42895 45291
1 29407
1 9103
2 5324 6026
1 31374
2 5841 29212
2 23318 30169
0
2 25579 21864
1 32335
2 23800 806
2 25593 11060
2 15157 69
1 34355
2 2925 14080
2 33167 18126
2 7104 5549
2 40443 5056
2 28415 696
1 4790
1 7018
2 3471 21650
2 2916 40765
1 34240
2 42308 18364
1 38483
0
2 1698 11488
1 ...

output:

42895

result:

ok single line: '42895'

Test #19:

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

input:

2 2 2
1 2
2 2 1
1 1
2 1 2
2 1 2
1 1

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 4ms
memory: 5772kb

input:

2 2 2
1 2
2 2 1
1 2
2 2 1
2 2 1
1 2

output:

2

result:

ok single line: '2'

Test #21:

score: 0
Accepted
time: 34ms
memory: 19556kb

input:

19293 19293 19293
2 15559 6355
2 18678 12383
2 10518 2914
2 9321 5480
2 2515 9636
2 348 6411
2 8068 5686
2 13171 5869
2 3983 3883
2 11207 18235
2 6332 13692
2 9259 8353
2 18013 1039
2 14419 10593
2 14504 3897
2 3936 12241
2 7111 14415
2 9387 11892
2 6697 4039
2 8091 9046
2 4286 14361
2 17222 5305
2 ...

output:

28939

result:

ok single line: '28939'

Test #22:

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

input:

20 20 20
1 1
2 1 2
2 2 3
2 3 4
2 4 5
1 6
2 6 7
2 7 8
2 8 9
2 9 10
1 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
0
0
0
0
1 1
2 1 2
2 2 3
2 3 4
2 4 5
1 6
2 6 7
2 7 8
2 8 9
2 9 10
1 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
0
0
0
0
1 1
2 1 2
2 2 3
2 3 4
2 4 5
1 6
2 6 7
2 7 8
2 8 9
2 9 10
1 11
2 11 12
2...

output:

22

result:

ok single line: '22'

Test #23:

score: 0
Accepted
time: 5ms
memory: 4300kb

input:

1000 1000 1000
1 1
2 1 2
2 2 3
2 3 4
2 4 5
2 5 6
2 6 7
2 7 8
2 8 9
2 9 10
2 10 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
2 16 17
2 17 18
2 18 19
2 19 20
2 20 21
1 22
2 22 23
2 23 24
2 24 25
2 25 26
2 26 27
2 27 28
2 28 29
2 29 30
2 30 31
2 31 32
2 32 33
2 33 34
2 34 35
2 35 36
2 36 37
2 37 38
2 38 ...

output:

1292

result:

ok single line: '1292'

Test #24:

score: 0
Accepted
time: 30ms
memory: 10072kb

input:

42099 49103 43206
2 2436 21573
2 9996 23380
2 18655 46120
2 12927 46150
2 40795 5903
2 21860 35021
2 35508 10085
2 15704 5818
2 4284 22266
2 21850 28412
2 25375 24412
2 5997 38671
2 14067 26688
2 29986 225
2 8819 39574
2 28550 12704
2 6055 4336
2 14012 21939
2 13223 10017
2 36352 23453
2 41234 13597...

output:

6

result:

ok single line: '6'

Test #25:

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

input:

50000 50000 50000
1 1
2 1 2
2 2 3
2 3 4
2 4 5
2 5 6
2 6 7
2 7 8
2 8 9
2 9 10
2 10 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
2 16 17
2 17 18
2 18 19
2 19 20
2 20 21
2 21 22
2 22 23
2 23 24
2 24 25
2 25 26
2 26 27
2 27 28
2 28 29
2 29 30
2 30 31
2 31 32
2 32 33
2 33 34
2 34 35
2 35 36
2 36 37
2 37 38...

output:

65098

result:

ok single line: '65098'

Test #26:

score: 0
Accepted
time: 5ms
memory: 4180kb

input:

797 781 965
2 542 265
2 613 195
2 483 758
2 387 62
2 9 45
2 146 38
2 305 457
2 374 18
2 776 273
2 475 432
2 691 108
2 264 284
2 70 598
2 741 673
2 393 480
2 250 145
2 740 748
2 35 221
2 442 229
2 204 326
2 304 538
2 721 685
2 58 778
2 51 740
2 750 227
2 25 389
2 142 462
2 557 370
2 30 147
2 28 300
2...

output:

960

result:

ok single line: '960'

Test #27:

score: 0
Accepted
time: 76ms
memory: 30640kb

input:

48703 42977 49346
2 8620 24764
2 14087 32876
0
2 8945 5627
2 41296 34519
0
2 29062 5131
2 816 1371
2 29401 1787
0
2 10358 19458
2 611 26890
2 32600 33419
2 7484 25258
2 18804 27934
2 40145 24038
2 10559 8176
2 17733 7525
2 12422 37383
2 1438 41231
2 40252 30643
0
0
2 6532 38724
2 19246 9753
2 19848 ...

output:

56108

result:

ok single line: '56108'

Test #28:

score: 0
Accepted
time: 5ms
memory: 4152kb

input:

802 787 751
2 138 295
2 572 302
2 575 580
2 556 248
2 642 441
2 638 379
2 650 79
2 397 313
2 464 757
2 753 483
2 461 61
2 506 367
2 582 62
2 350 616
2 19 284
2 196 658
2 483 683
2 588 526
2 106 333
2 478 23
2 640 442
2 781 525
2 362 193
2 323 691
2 648 627
2 784 355
2 399 51
2 662 105
2 107 53
2 417...

output:

928

result:

ok single line: '928'

Test #29:

score: 0
Accepted
time: 57ms
memory: 29380kb

input:

41866 41104 47356
2 14498 27153
2 11889 11501
2 24507 26825
2 9375 38374
2 36646 26596
2 27810 2781
2 18125 31616
2 28814 7751
2 3726 32390
2 24020 9158
2 23175 26847
2 30193 20375
2 33609 14680
2 12657 26318
2 36465 1173
2 40844 30906
0
2 17851 11228
2 15337 33580
0
2 35061 16536
2 1967 3490
2 1256...

output:

54184

result:

ok single line: '54184'

Test #30:

score: 0
Accepted
time: 5ms
memory: 4104kb

input:

849 766 854
1 150
2 721 416
2 716 277
1 336
2 471 535
1 621
2 661 638
2 201 751
0
2 705 67
2 350 24
2 118 131
2 124 704
2 66 511
2 577 200
2 406 733
2 749 312
0
2 114 168
2 472 18
2 83 398
2 261 591
2 627 433
2 60 454
2 371 351
2 70 706
2 143 35
2 477 133
2 365 38
1 126
1 525
2 587 74
0
2 162 225
2 ...

output:

935

result:

ok single line: '935'

Test #31:

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

input:

40473 42204 46693
2 17306 29840
2 21655 27206
2 1577 30755
2 9303 38135
2 13899 38726
2 25718 5486
0
2 13674 32709
2 3258 1310
2 19078 6271
2 32222 38810
2 18668 28018
2 9005 31601
2 31888 40637
2 32991 7539
2 40415 29067
2 33572 39589
2 26823 19361
2 38360 8413
2 4352 12745
2 40742 38924
2 14996 19...

output:

53046

result:

ok single line: '53046'

Test #32:

score: -100
Wrong Answer
time: 4ms
memory: 3668kb

input:

3 3 3
2 3 1
2 2 1
2 3 2
2 1 3
2 2 3
2 1 2
2 2 3
2 1 2
2 1 3

output:

5

result:

wrong answer 1st lines differ - expected: '4', found: '5'
English 繁體中文 简体中文

Server Time: 2024-12-02 15:00:12 | OpenSource Project