QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#722496 | #2722. Marshmallow Molecules | SimonLJK | 5 | 11ms | 5640kb | C++17 | 764b | 2024-11-07 19:15:00 | 2024-11-07 19:15:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+99;
int n,m;
struct edge{
int v,nxt;
}edg[N];
int cntedge,hd[N];
void add(int u,int v){
edg[++cntedge]=(edge){v,hd[u]};
hd[u]=cntedge;
}
int id[N],sz[N];
int find(int x){
if(id[x]==x) return x;
return id[x]=find(id[x]);
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
int u,v;
for(int i=1;i<=m;i++){
cin>>u>>v;
add(u,v);
}
for(int i=1;i<=n;i++) id[i]=i,sz[i]=1;
int fu,fv;
long long ans=0;
for(u=1;u<=n;u++){
sz[find(u)]--;
ans+=sz[find(u)];
for(int i=hd[u];i;i=edg[i].nxt){
v=edg[i].v;
fu=find(u); fv=find(v);
if(fu==fv) continue;
ans++;
id[fv]=fu; sz[fu]+=sz[fv];
}
}
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 1ms
memory: 3700kb
input:
100 4900 15 25 10 36 87 93 60 75 43 62 12 16 53 62 5 32 15 87 20 96 84 89 58 91 12 49 66 91 6 17 56 85 11 72 44 82 25 69 1 42 40 62 5 83 39 99 52 92 28 47 34 72 33 62 4 84 34 52 55 62 38 69 36 69 82 91 40 50 69 85 33 66 41 44 28 60 96 100 41 74 42 50 28 36 61 89 54 99 44 86 45 61 24 75 20 31 23 29 6...
output:
4948
result:
ok single line: '4948'
Test #2:
score: 0
Wrong Answer
time: 1ms
memory: 3668kb
input:
100 2000 30 54 4 27 67 70 75 88 94 96 37 56 6 19 29 59 31 70 34 99 18 69 39 79 47 63 14 90 37 45 50 94 36 41 80 100 68 71 10 92 37 75 34 91 69 91 59 63 53 85 54 86 64 79 57 96 66 96 31 38 27 80 12 25 35 63 5 99 28 61 57 71 10 81 21 43 44 49 37 52 35 100 64 94 67 90 35 46 54 91 38 77 25 40 6 80 6 60 ...
output:
4712
result:
wrong answer 1st lines differ - expected: '4721', found: '4712'
Subtask #2:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 10ms
memory: 4560kb
input:
5000 100000 1007 2107 610 4713 352 2900 1869 2260 3688 4056 1528 4136 1021 4034 1654 2324 799 3245 4575 4615 3552 4045 2322 3284 2287 3417 1619 4398 901 1538 2545 4698 3300 4618 2273 4855 1890 2475 2433 3158 653 2221 284 1845 3225 3573 1451 3707 1074 4210 284 3646 729 3732 2554 3901 3232 3513 2649 3...
output:
11589666
result:
wrong answer 1st lines differ - expected: '11309962', found: '11589666'
Subtask #3:
score: 5
Accepted
Test #26:
score: 5
Accepted
time: 11ms
memory: 5472kb
input:
100000 99020 2976 97036 5108 36137 82 903 11925 33740 30856 70930 4105 43498 5500 66211 13684 81739 3416 70119 5792 89390 23098 83444 5033 27428 24910 64719 1714 51173 13329 34411 3859 33637 4127 33246 181 46040 8259 93728 1881 32818 604 47012 12645 65438 8226 19448 7637 87170 2828 70329 243 7934 44...
output:
3851818389
result:
ok single line: '3851818389'
Test #27:
score: 5
Accepted
time: 11ms
memory: 5592kb
input:
100000 99893 1719 75153 237 35956 16388 19581 14378 78657 69903 84628 58266 58297 320 45250 2164 94317 13451 17062 73014 98393 5041 5082 15462 21916 38735 80715 7245 21268 33986 98231 2245 28788 31001 73166 74515 94536 66148 72235 800 2507 45065 46517 15955 64664 4758 51907 18105 22123 17499 74852 3...
output:
2462112722
result:
ok single line: '2462112722'
Test #28:
score: 5
Accepted
time: 11ms
memory: 5508kb
input:
100000 99900 3215 11099 41057 60010 30319 66637 42476 84769 66980 68240 84489 96888 30255 36867 15772 18310 37275 47722 35210 39664 36975 43180 52829 86179 69326 95686 6352 14441 45670 51396 50368 51411 1817 3167 38972 45081 21316 33467 79960 85622 89183 91753 6661 10531 52574 70802 24353 27151 7889...
output:
1230469117
result:
ok single line: '1230469117'
Test #29:
score: 5
Accepted
time: 11ms
memory: 5460kb
input:
100000 98979 6146 34482 5140 86086 15474 73948 97 16533 9889 61282 1880 75753 4975 96342 59 3976 201 45655 8672 86427 2312 24929 24243 86289 692 30146 717 47964 20606 73190 12483 73291 21841 95121 6529 46724 1170 24787 974 14021 13242 35132 133 2714 12539 71980 26588 85706 1252 9415 2417 27116 1301 ...
output:
3232411268
result:
ok single line: '3232411268'
Test #30:
score: 5
Accepted
time: 7ms
memory: 5528kb
input:
100000 99910 363 1509 46092 55973 1282 4663 66733 99422 4471 7278 46679 73220 8724 88050 36959 76558 32919 92312 2201 4437 1633 11029 50837 89041 12188 81117 27592 57859 232 811 21537 72260 133 140 7744 19173 39664 55781 67413 71464 56750 99720 20401 61461 32373 76547 23791 56062 13778 19928 45972 7...
output:
2481369952
result:
ok single line: '2481369952'
Test #31:
score: 5
Accepted
time: 11ms
memory: 5508kb
input:
100000 99894 20586 22241 83458 92563 4793 4876 15416 17413 77379 86271 49068 72690 5554 8984 67850 79522 57928 65580 3202 3529 7253 10135 53243 55945 55563 68379 26173 29069 32887 39945 30809 49823 95154 99866 61659 71168 26549 60990 26015 32060 48853 84428 3340 8574 58338 61441 38161 73381 3676 603...
output:
1219197484
result:
ok single line: '1219197484'
Test #32:
score: 5
Accepted
time: 11ms
memory: 5448kb
input:
100000 98974 5738 64383 8540 93600 19635 52609 25378 65021 201 6811 5663 63923 5533 59688 1474 33612 5573 55949 1570 5494 24037 91262 983 50443 3081 76641 830 21043 18059 89653 17033 78741 13668 46052 155 953 1943 53063 26763 76507 1394 88357 10513 91646 5612 88789 7319 68247 22305 69952 13238 54515...
output:
4037175909
result:
ok single line: '4037175909'
Test #33:
score: 5
Accepted
time: 11ms
memory: 5512kb
input:
100000 99920 15367 29210 38519 69788 8567 28914 2382 38225 21008 60979 94538 97337 1845 6708 33576 45151 34386 91697 1765 3925 29178 83337 24962 29739 2106 2447 12232 14923 15690 83453 6179 25460 45939 87298 928 2928 21451 90309 18722 23982 4147 21506 39014 53802 8209 10244 17174 32060 1855 3740 268...
output:
2481130031
result:
ok single line: '2481130031'
Test #34:
score: 5
Accepted
time: 7ms
memory: 5640kb
input:
100000 99904 44171 49968 58010 87940 18741 35900 25812 56653 15973 18946 7421 11516 26622 48349 10351 18213 40578 44743 18453 22132 42593 58917 49709 57808 59175 70545 24896 25874 47624 84036 40647 42405 69770 75103 19126 29273 56799 58873 3002 3253 7618 10423 40215 40351 25280 44598 49417 74247 493...
output:
1164946111
result:
ok single line: '1164946111'
Test #35:
score: 5
Accepted
time: 11ms
memory: 5468kb
input:
100000 98998 5034 37396 7531 76242 907 22776 1136 17936 5499 31369 11567 73607 2646 82050 5328 25550 19206 89978 4805 26562 298 6341 6038 38219 2572 31407 2646 11809 7625 32723 15561 96975 814 18391 2989 34013 850 8155 11060 86255 124 1832 68 18979 17362 57933 4273 83311 15846 56183 18375 85415 1207...
output:
4016504110
result:
ok single line: '4016504110'
Test #36:
score: 5
Accepted
time: 11ms
memory: 5592kb
input:
100000 99904 34 28894 14959 24183 74569 80751 13227 21322 76772 94480 2024 2382 11039 51608 2065 31148 19164 72488 5984 54363 11319 14262 3786 35337 54105 92939 15970 85191 33625 38563 9021 96191 75727 81703 14217 82816 43198 82609 18276 64739 2509 27281 5267 9618 30926 75962 33583 68063 82270 94683...
output:
2483186538
result:
ok single line: '2483186538'
Test #37:
score: 5
Accepted
time: 11ms
memory: 5632kb
input:
100000 99886 50108 53909 17497 32406 30592 34527 35107 36052 27363 44558 8815 13175 59334 59827 13576 13676 43324 57846 13469 14695 55393 64420 28240 30872 44504 58694 84869 86404 80988 93101 9694 19133 13191 21837 13030 14270 4651 5410 19915 20438 38755 43997 68228 95508 80645 85558 39218 50624 129...
output:
1114405226
result:
ok single line: '1114405226'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%