QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110673#4639. 食物链bpan_409630 66ms3956kbC++143.1kb2023-06-03 11:57:502023-06-03 11:57:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-03 11:57:53]
  • 评测
  • 测评结果：30
  • 用时：66ms
  • 内存：3956kb
查看
  • [2023-06-03 11:57:50]
  • 提交

answer

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <map>
#include <set>
using namespace std;
int opposite[500001], parent[500001], sz[500001];
int answer = 0;

int find(int x) {
    if (parent[x] != x) {
        int temp = parent[x];
        find(temp);
        parent[x] = parent[temp];
    }
    return parent[x];
}

bool join(int x, int y) {
    int fx = find(x), fy = find(y);
    if (sz[fx] <= sz[fy]) {
        parent[fx] = fy;
        sz[fy] += sz[fx];
        if (opposite[find(x)] != -1 && find(opposite[find(x)]) == find(find(y))) {
            answer ++;
            return false;
        }
        if (opposite[find(y)] != -1 && find(opposite[find(y)]) == find(x)) {
            answer ++;
            return false;
        }
        if (find(opposite[fx]) != find(opposite[fy])) {
            if (!join(fx, fy)) {
                parent[fx] = fx;
                sz[fy] -= fx;
                return false;
            }
        }
    }
    else {
        parent[fy] = fx;
        sz[fx] += sz[fy];
        if (opposite[find(x)] != -1 && find(opposite[find(x)]) == find(find(y))) {
            answer ++;
            return false;
        }
        if (opposite[find(y)] != -1 && find(opposite[find(y)]) == find(x)) {
            answer ++;
            return false;
        }
        if (find(opposite[fx]) != find(opposite[fy])) {
            if (!join(fx, fy)) {
                parent[fy] = fy;
                sz[fx] -= fy;
                return false;
            }
        }
    }
    
    
    return true;
}

int main() {
    //freopen("eat.in", "r", stdin);
    //freopen("eat.out", "w", stdout);
    //cout << "a" << endl;
    int N, K; cin >> N >> K;
    for (int i = 1; i <= N; i ++) {
        sz[i] = 1;
        parent[i] = i;
        opposite[i] = -1;
    }
    for (int i = 0; i < K; i ++) {
        int type, x, y; cin >> type >> x >> y;
        if (x > N || y > N) {
            answer ++;
            continue;
        }
        if (type == 1) {
            if (opposite[find(x)] != -1 && find(opposite[find(x)]) == find(find(y))) {
                answer ++;
                continue;
            }
            if (opposite[find(y)] != -1 && find(opposite[find(y)]) == find(x)) {
                answer ++;
                continue;
            }
            join(x, y);
        }
        else {
            if (opposite[x] == -1) {
                if (find(x) == find(y)) {
                    answer ++; continue;
                }
                //cout << "x" << endl;
                opposite[find(x)] = find(y);
            }
            else {
                if (find(opposite[find(x)]) == find(opposite[find(y)])) {
                    answer ++; continue;
                }
                if (find(x) == find(y)) {
                    answer ++; continue;
                }
                if (find(x) == find(opposite[find(y)])) {
                    answer ++; continue;
                }
                join(y, opposite[x]);
            }
        }
    }
    cout << answer << endl;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 3ms
memory: 3404kb

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: 2ms
memory: 3536kb

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: 0
Wrong Answer
time: 2ms
memory: 3408kb

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:

115

result:

wrong answer 1st lines differ - expected: '154', found: '115'

Test #4:

score: 0
Wrong Answer
time: 5ms
memory: 3380kb

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:

1272

result:

wrong answer 1st lines differ - expected: '1804', found: '1272'

Test #5:

score: 0
Wrong Answer
time: 8ms
memory: 3548kb

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:

797

result:

wrong answer 1st lines differ - expected: '1988', found: '797'

Test #6:

score: 0
Wrong Answer
time: 3ms
memory: 3388kb

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:

131

result:

wrong answer 1st lines differ - expected: '781', found: '131'

Test #7:

score: 0
Wrong Answer
time: 21ms
memory: 3404kb

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:

0

result:

wrong answer 1st lines differ - expected: '2310', found: '0'

Test #8:

score: 0
Wrong Answer
time: 66ms
memory: 3464kb

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:

0

result:

wrong answer 1st lines differ - expected: '2635', found: '0'

Test #9:

score: 0
Wrong Answer
time: 52ms
memory: 3616kb

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:

0

result:

wrong answer 1st lines differ - expected: '1322', found: '0'

Test #10:

score: 10
Accepted
time: 32ms
memory: 3956kb

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 07:48:51 | OpenSource Project