QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#487366#4639. 食物链Tad100 ✓14ms4848kbC++201.2kb2024-07-22 20:39:202024-07-22 20:39:21

Judging History

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

  • [2024-07-22 20:39:21]
  • 评测
  • 测评结果：100
  • 用时：14ms
  • 内存：4848kb
查看
  • [2024-07-22 20:39:20]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

int dad[150000],high[150000]={1};

int n,k,h=0;

int fr(int x){

    int r=x,i=x,j;

    while(dad[r]!=r){
        r=dad[r];
    }

    while(i!=r){
        j=dad[i];
        dad[i]=r;
        i=j;
    }

    return i;
}
void me(int x,int y){

    int xr=fr(x),yr=fr(y);

    if(xr==yr) return ;
    if(high[xr]==high[yr]) high[yr]++;
    else if(high[xr]>high[yr]) swap(high[xr],high[yr]);

    dad[xr]=yr;

}
int main () {

    int i,j,d,x,y;
    cin>>n>>k;

    for(i=1;i<=n*3;i++){
        dad[i]=i;
    } 

    for(i=1;i<=k;++i){

        scanf("%d%d%d",&d,&x,&y);

        if(x>n||y>n){
            h++;
            continue;
        }

        if(d==1){
            if(fr(x+n)==fr(y)||fr(x+n*2)==fr(y)){
                h++;
                continue;
            }

            me(x,y);
            me(x+n,y+n);
            me(x+2*n,y+2*n);

        } 
        else if(d==2){

            if(fr(x)==fr(y)||fr(x+n*2)==fr(y)){
                h++;
                continue;
            }

            me(x,y+2*n);  
            me(x+n,y);
            me(x+n*2,y+n);

        }

    }

    cout<<h;
    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 3624kb

input:

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

output:

3

result:

ok single line: '3'

Test #2:

score: 10
Accepted
time: 0ms
memory: 3804kb

input:

1 10
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5
1 6 6
1 7 7
1 8 8
1 9 9
1 10 10

output:

9

result:

ok single line: '9'

Test #3:

score: 10
Accepted
time: 0ms
memory: 3872kb

input:

80 300
1 38 13
2 9 34
2 62 52
2 64 74
2 80 18
2 31 14
2 23 22
2 41 30
2 60 12
2 80 81
2 18 35
1 53 76
2 9 58
1 9 14
1 28 30
2 49 9
2 65 24
1 30 69
2 79 27
2 32 58
2 59 49
2 26 15
1 65 8
2 11 65
2 65 75
1 67 73
2 19 19
2 50 10
2 25 34
1 68 9
2 54 50
1 13 34
2 78 21
2 40 1
2 55 2
2 38 36
1 81 30
2 45 ...

output:

154

result:

ok single line: '154'

Test #4:

score: 10
Accepted
time: 1ms
memory: 3752kb

input:

160 3000
1 127 88
1 37 112
2 130 95
1 94 137
2 32 79
1 150 89
2 32 122
2 25 119
2 43 155
1 157 54
1 134 159
2 18 17
2 124 76
2 130 22
1 78 63
2 1 158
2 56 12
2 61 19
2 69 72
1 18 113
1 7 127
2 129 21
2 47 26
2 88 104
1 64 14
1 107 21
2 151 139
1 20 93
2 154 55
2 65 56
2 100 78
2 152 137
2 98 30
2 12...

output:

1804

result:

ok single line: '1804'

Test #5:

score: 10
Accepted
time: 1ms
memory: 3884kb

input:

400 6000
2 214 343
1 217 161
1 301 359
2 6 304
1 315 182
1 390 345
1 98 387
1 172 67
2 157 237
2 215 23
2 371 183
2 24 45
2 40 125
2 295 34
2 358 64
1 72 1
1 11 196
2 286 275
1 59 372
2 254 303
1 55 119
1 225 85
2 322 298
2 101 236
2 189 61
2 64 244
1 184 219
1 171 227
2 148 375
2 64 392
2 288 192
1...

output:

1988

result:

ok single line: '1988'

Test #6:

score: 10
Accepted
time: 2ms
memory: 3672kb

input:

1000 10000
1 607 607
1 587 192
1 15 324
2 890 857
1 110 79
1 495 757
2 149 661
2 373 370
2 488 164
1 73 183
1 66 362
2 496 122
2 426 377
1 743 768
2 364 399
1 816 625
1 859 516
1 68 18
2 307 66
2 715 493
1 334 657
2 198 262
1 483 151
1 808 243
1 819 727
1 526 365
2 83 34
2 933 151
1 983 244
2 984 23...

output:

781

result:

ok single line: '781'

Test #7:

score: 10
Accepted
time: 4ms
memory: 3684kb

input:

2000 50000
1 1805 1220
1 1608 1681
2 522 456
2 1224 989
2 1846 554
2 1669 1328
2 1683 1562
2 1286 361
1 1151 431
2 1973 752
2 1676 1657
2 419 616
1 525 1766
2 739 1118
2 603 219
2 1877 941
1 844 1740
1 1648 1327
1 41 1288
2 308 502
2 536 1705
1 915 1934
2 279 961
2 797 171
2 775 324
1 1755 463
2 278...

output:

2310

result:

ok single line: '2310'

Test #8:

score: 10
Accepted
time: 12ms
memory: 3704kb

input:

3000 80000
2 2593 1652
2 1934 339
2 2800 1605
1 2214 1212
2 1659 2576
2 1174 1694
2 2340 1568
2 1473 1561
2 2600 788
1 1013 2938
2 357 2266
2 580 2156
1 2053 294
1 98 2940
2 64 338
2 2265 5
2 1672 1663
2 360 1435
2 1285 2051
2 1074 387
1 190 893
2 930 2524
1 1806 897
1 1030 1818
1 907 2289
2 379 232...

output:

2635

result:

ok single line: '2635'

Test #9:

score: 10
Accepted
time: 14ms
memory: 3924kb

input:

6000 100000
2 4625 862
2 2788 4751
2 1580 1618
2 259 5130
2 5878 2956
2 1469 3285
2 5134 258
2 2723 2910
2 4793 1140
2 2626 1264
2 3866 2759
2 943 98
1 2963 5668
2 2907 3126
2 3417 4303
1 3307 5623
2 157 1277
1 1267 2732
2 5316 3735
2 5425 2357
1 3560 3585
2 436 3714
2 355 4634
2 4981 2763
2 2142 98...

output:

1322

result:

ok single line: '1322'

Test #10:

score: 10
Accepted
time: 11ms
memory: 4848kb

input:

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

output:

71

result:

ok single line: '71'
English 繁體中文 简体中文

Server Time: 2024-11-30 05:59:21 | OpenSource Project