QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#140364 | #2527. Ink Mix | jaker | AC ✓ | 188ms | 28616kb | C++14 | 1.9kb | 2023-08-15 19:45:50 | 2023-08-15 19:47:14 |
Judging History
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'