QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#140364#2527. Ink MixjakerAC ✓188ms28616kbC++141.9kb2023-08-15 19:45:502023-08-15 19:47:14

Judging History

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

  • [2023-08-15 19:47:14]
  • 评测
  • 测评结果:AC
  • 用时:188ms
  • 内存:28616kb
  • [2023-08-15 19:45:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define ll long long
const int maxn = 101000;
int n,m,k;
vector<int> G[maxn] , R[maxn] , son[maxn];
int ufs[maxn];
int idom[maxn] , sdom[maxn] , anc[maxn];
int p[maxn] , dfn[maxn] , id[maxn] , tim;
int rd() {
    int x; scanf("%d",&x);
    return x;
}
int findufs(int x) {
    if( ufs[x] == x ) return x;
    int t = ufs[x]; ufs[x] = findufs( ufs[x] );
    if( dfn[ sdom[anc[x]] ] > dfn[ sdom[anc[t]] ] )
        anc[x] = anc[t];
    return ufs[x];
}
void dfs(int x) {
    dfn[x] = ++tim; id[tim] = x; sdom[x] = x;
    for( int y : G[x] ) if(!dfn[y]) {
        p[y] = x; dfs(y);
    }
}
void get_dominator(int n) {
    for(int i = 1;i <= n;++i) ufs[i] = anc[i] = i;
    dfs(1);
    for(int i = n;i > 1;--i) {
        int x = id[i];
        for( int y : R[x] ) if( dfn[y] ) {
            findufs(y);
            if( dfn[sdom[x]] > dfn[sdom[anc[y]]] )
                sdom[x] = sdom[anc[y]];
        }
        son[sdom[x]].push_back( x );  ufs[x] = p[x];
        for( int u : son[p[x]] ) {
            findufs(u);
            idom[u] = ( sdom[u] == sdom[anc[u]] ? p[x] : anc[u] );
        }
        son[p[x]].clear();
    }
    for(int i = 2;i <= n;++i) {
        int x = id[i];
        if( idom[x] != sdom[x] ) idom[x] = idom[idom[x]];
        son[idom[x]].push_back(x);
    }
}
bool vis[maxn];
int main(){
    n = rd(); m = rd(); k = rd();
    rep(i,1,k) {
        int x = rd(),y = rd();
        G[x+1].push_back(y+1);
        R[y+1].push_back(x+1);
    }
    rep(i,1,m) {
        G[1].push_back( i+1 );
        R[i+1].push_back( 1 );
    }
    n++;
    get_dominator(n);
    int ans = n-1;
    rep(x,2,n) if(!dfn[x]) vis[x] = true,  ans--;
    rep(x,2,n) {
        for(auto y:son[x])
            if(!vis[y]) vis[y] = true , ans--;
    }
    printf("%d\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 12460kb

input:

5 2 3
1 3
2 3
2 4

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 138ms
memory: 25080kb

input:

100000 1000 500000
34858 17953
55995 73239
95582 64046
51349 21545
69784 91636
91522 54658
40233 28256
13245 1994
61368 90709
2201 36962
91792 27658
26011 65416
88717 89805
7110 59833
40831 31578
83666 66050
29872 83584
40425 3888
3665 12942
97331 84900
12058 52500
23976 93303
84628 11138
20779 5102...

output:

95834

result:

ok single line: '95834'

Test #3:

score: 0
Accepted
time: 171ms
memory: 25096kb

input:

100000 1000 500000
83934 92552
41176 48146
95872 11566
16491 15026
57930 55348
69435 42655
54091 77007
39652 61497
95909 94214
81536 18831
22735 3477
84230 46230
60089 93253
39467 91087
52293 49276
86302 47024
5931 4956
25018 95346
77938 1268
39635 30527
39297 63750
84511 51485
19157 34383
6771 1519...

output:

95870

result:

ok single line: '95870'

Test #4:

score: 0
Accepted
time: 159ms
memory: 25184kb

input:

100000 1000 500000
69361 46081
76497 42982
53186 1997
78313 41220
26031 16636
11914 13932
60265 20678
40012 73224
17204 91468
57679 41215
85394 6213
26790 129
12727 47781
54797 10413
53074 32450
8896 76388
94316 1479
10047 67969
38233 82284
68305 80567
85861 94614
60359 39691
56836 30769
40430 21923...

output:

95992

result:

ok single line: '95992'

Test #5:

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

input:

100000 1000 500000
9598 94990
53390 29784
69390 6582
61200 72883
18914 62757
32944 17178
94119 63272
11640 7341
26012 24957
949 34214
25751 52098
90238 94081
4124 53428
48201 20572
89951 67087
63338 37932
13655 93583
19770 79948
73693 18756
75078 59018
35873 90241
88185 51429
11499 37474
96825 57894...

output:

95866

result:

ok single line: '95866'

Test #6:

score: 0
Accepted
time: 166ms
memory: 23152kb

input:

100000 1000 500000
8863 14812
3636 94905
19362 22791
22178 69373
18418 62991
61064 99529
25345 34780
25887 62114
24856 40481
20987 66757
66842 70410
54057 66332
57268 70057
31805 96811
12294 48905
11022 18521
73668 81772
2674 33244
28329 80446
12183 25609
70738 90147
42760 94427
38790 56335
51946 76...

output:

61490

result:

ok single line: '61490'

Test #7:

score: 0
Accepted
time: 146ms
memory: 23152kb

input:

100000 1000 500000
28180 54591
62658 92760
12437 26620
35095 44068
49359 89369
18552 97525
25243 76675
69228 73823
79207 89995
86182 96153
18789 88554
45884 69402
50106 87863
28153 99765
69134 98201
2473 64160
18742 26168
1758 33544
71238 91102
36872 96124
32461 94096
24875 96757
36545 78165
35704 3...

output:

61168

result:

ok single line: '61168'

Test #8:

score: 0
Accepted
time: 127ms
memory: 23376kb

input:

100000 1000 500000
56769 60531
79001 97901
3614 77124
68131 91052
87620 89106
11610 18092
9196 65864
58451 92717
5173 88946
36408 89437
36373 56370
25882 81186
41706 70697
58313 69190
46903 99153
8022 73965
46021 72960
79075 96317
3695 70431
19340 56559
58405 75753
78623 84752
79418 94857
40139 4354...

output:

61409

result:

ok single line: '61409'

Test #9:

score: 0
Accepted
time: 128ms
memory: 23396kb

input:

100000 1000 500000
1311 70132
21413 61384
32352 66624
2674 64707
63489 81114
50651 90806
11120 61126
24366 32953
32652 76787
2755 91401
21669 21957
89875 92630
10884 39362
49059 95251
6579 68404
26656 64967
25003 90212
14068 28032
37363 51137
68867 82496
30298 42963
91715 92822
82705 84714
41406 883...

output:

61576

result:

ok single line: '61576'

Test #10:

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

input:

4 2 3
1 3
2 3
2 4

output:

3

result:

ok single line: '3'

Test #11:

score: 0
Accepted
time: 143ms
memory: 23148kb

input:

100000 1000 500000
81478 96768
47268 47286
41511 77578
1614 67888
25392 81845
29743 62464
37087 41538
35884 55471
38069 68687
447 20883
4350 27107
8416 53206
25761 94536
26409 51977
34066 72388
29336 45776
42375 56585
49242 89561
9640 29558
64280 91913
14041 70360
17366 40798
24546 31773
5222 54180
...

output:

60881

result:

ok single line: '60881'

Test #12:

score: 0
Accepted
time: 137ms
memory: 26492kb

input:

100000 1000 500000
1 1
1 2
2 1
2 3
3 1
3 4
4 1
4 5
5 1
5 6
6 1
6 7
7 1
7 8
8 1
8 9
9 1
9 10
10 1
10 11
11 1
11 12
12 1
12 13
13 1
13 14
14 1
14 15
15 1
15 16
16 1
16 17
17 1
17 18
18 1
18 19
19 1
19 20
20 1
20 21
21 1
21 22
22 1
22 23
23 1
23 24
24 1
24 25
25 1
25 26
26 1
26 27
27 1
27 28
28 1
28 29...

output:

84438

result:

ok single line: '84438'

Test #13:

score: 0
Accepted
time: 3ms
memory: 12704kb

input:

5 2 4
1 3
1 4
2 3
2 4

output:

4

result:

ok single line: '4'

Test #14:

score: 0
Accepted
time: 137ms
memory: 26672kb

input:

100000 1000 500000
1 1
1 2
2 1
2 3
3 1
3 4
4 1
4 5
5 1
5 6
6 1
6 7
7 1
7 8
8 1
8 9
9 1
9 10
10 1
10 11
11 1
11 12
12 1
12 13
13 1
13 14
14 1
14 15
15 1
15 16
16 1
16 17
17 1
17 18
18 1
18 19
19 1
19 20
20 1
20 21
21 1
21 22
22 1
22 23
23 1
23 24
24 1
24 25
25 1
25 26
26 1
26 27
27 1
27 28
28 1
28 29...

output:

84255

result:

ok single line: '84255'

Test #15:

score: 0
Accepted
time: 116ms
memory: 26532kb

input:

100000 1000 500000
1 1
1 2
2 1
2 3
3 1
3 4
4 1
4 5
5 1
5 6
6 1
6 7
7 1
7 8
8 1
8 9
9 1
9 10
10 1
10 11
11 1
11 12
12 1
12 13
13 1
13 14
14 1
14 15
15 1
15 16
16 1
16 17
17 1
17 18
18 1
18 19
19 1
19 20
20 1
20 21
21 1
21 22
22 1
22 23
23 1
23 24
24 1
24 25
25 1
25 26
26 1
26 27
27 1
27 28
28 1
28 29...

output:

84457

result:

ok single line: '84457'

Test #16:

score: 0
Accepted
time: 131ms
memory: 26576kb

input:

100000 1000 500000
1 1
1 2
2 1
2 3
3 1
3 4
4 1
4 5
5 1
5 6
6 1
6 7
7 1
7 8
8 1
8 9
9 1
9 10
10 1
10 11
11 1
11 12
12 1
12 13
13 1
13 14
14 1
14 15
15 1
15 16
16 1
16 17
17 1
17 18
18 1
18 19
19 1
19 20
20 1
20 21
21 1
21 22
22 1
22 23
23 1
23 24
24 1
24 25
25 1
25 26
26 1
26 27
27 1
27 28
28 1
28 29...

output:

84370

result:

ok single line: '84370'

Test #17:

score: 0
Accepted
time: 151ms
memory: 26832kb

input:

100000 1000 500000
1 1
1 2
2 1
2 3
3 1
3 4
4 1
4 5
5 1
5 6
6 1
6 7
7 1
7 8
8 1
8 9
9 1
9 10
10 1
10 11
11 1
11 12
12 1
12 13
13 1
13 14
14 1
14 15
15 1
15 16
16 1
16 17
17 1
17 18
18 1
18 19
19 1
19 20
20 1
20 21
21 1
21 22
22 1
22 23
23 1
23 24
24 1
24 25
25 1
25 26
26 1
26 27
27 1
27 28
28 1
28 29...

output:

84270

result:

ok single line: '84270'

Test #18:

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

input:

100000 2 149999
1 50002
2 75000
3 4
4 50002
50002 3
4 5
5 50003
50003 4
5 6
6 50004
50004 5
6 7
7 50005
50005 6
7 8
8 50006
50006 7
8 9
9 50007
50007 8
9 10
10 50008
50008 9
10 11
11 50009
50009 10
11 12
12 50010
50010 11
12 13
13 50011
50011 12
13 14
14 50012
50012 13
14 15
15 50013
50013 14
15 16
...

output:

50003

result:

ok single line: '50003'

Test #19:

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

input:

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

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 81ms
memory: 28324kb

input:

100000 10000 500000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 ...

output:

10000

result:

ok single line: '10000'

Test #21:

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

input:

4 2 4
1 3
1 4
2 3
2 4

output:

4

result:

ok single line: '4'

Test #22:

score: 0
Accepted
time: 86ms
memory: 28616kb

input:

100000 10000 500000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 ...

output:

10000

result:

ok single line: '10000'

Test #23:

score: 0
Accepted
time: 94ms
memory: 28392kb

input:

100000 10000 500000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 ...

output:

10000

result:

ok single line: '10000'

Test #24:

score: 0
Accepted
time: 90ms
memory: 28376kb

input:

100000 10000 500000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 ...

output:

10000

result:

ok single line: '10000'

Test #25:

score: 0
Accepted
time: 78ms
memory: 28472kb

input:

100000 10000 500000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 ...

output:

10000

result:

ok single line: '10000'

Test #26:

score: 0
Accepted
time: 161ms
memory: 25112kb

input:

100000 1000 500000
64651 45884
55412 71631
23626 56435
10017 34015
23780 80085
42610 1128
84816 98269
41420 63301
61207 65243
69932 53257
24291 96331
87159 38354
363 88300
74623 72798
76247 39885
26481 6174
19852 53654
78574 71387
73900 31712
78314 98628
18527 58141
64005 84967
76215 88680
64963 775...

output:

95909

result:

ok single line: '95909'

Test #27:

score: 0
Accepted
time: 3ms
memory: 12824kb

input:

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

output:

2

result:

ok single line: '2'

Test #28:

score: 0
Accepted
time: 3ms
memory: 12800kb

input:

4 2 1
3 4

output:

2

result:

ok single line: '2'