QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#732785 | #6613. Bitwise Exclusive-OR Sequence | osir_ | AC ✓ | 456ms | 15212kb | C++17 | 2.9kb | 2024-11-10 15:53:34 | 2024-11-10 15:53:35 |
Judging History
answer
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
typedef struct node{
int u,v,w;
}node;
int n,m;
vector<node> edge;
void solve(){
cin>>n>>m;
for(int i=0;i<m;i++){
int u,v,w; cin>>u>>v>>w;
edge.emplace_back(node{u,v,w});
}
long long ans=0;
//把定义放在外面.
vector<pair<int,int>> vct[n+5];
vector<bool> vis1(n+5,false);
vector<int> col1(n+5);
for(int j=0;j<30;j++){
//统一在这里初始化,可以减少常数,直接从3s变为1s.
//qoj上面是跑了500ms.
//可以把30次压缩在一次dfs中,这样不用建图30次(100ms)..bfs应该也可以压缩?但是不会改..就这样凑合着吧,虽然说跑的慢一点,也能过吧..
for(int i=0;i<=n+1;i++) vct[i].clear(),vis1[i]=false,col1[i]=0;
for(int i=0;i<m;i++){
int u=edge[i].u,v=edge[i].v,w=edge[i].w;
if((w>>j)&1) vct[u].emplace_back(v,1),vct[v].emplace_back(u,1);
else vct[u].emplace_back(v,0),vct[v].emplace_back(u,0);
}
int res=0;
for(int i=1;i<=n;i++){
int res0=0,res1=0;
if(!vis1[i]){
vis1[i]=true;
col1[i]=1;
queue<int> que1;
que1.emplace(i);
res1++;
while(!que1.empty()){
int from=que1.front();
int color=col1[from];
que1.pop();
for(auto v:vct[from]){
if(!vis1[v.first]){
if(v.second==1){ //异色
que1.emplace(v.first);
if((color^1)==1) res1++;
else res0++;
col1[v.first]=color^1;
vis1[v.first]=true;
}
else{ //同色
que1.emplace(v.first);
if(color==1) res1++;
else res0++;
col1[v.first]=color;
vis1[v.first]=true;
}
}
else{
if(v.second==1&&col1[v.first]==color){ cout<<"-1"; return; }
else if(v.second==0&&col1[v.first]!=color){ cout<<"-1"; return; }
}
}
}
}
res+=min(res0,res1);
}
ans+=res*(1ll<<j);
}
cout<<ans;
}
int32_t main() {
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3824kb
input:
3 2 1 2 1 2 3 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
3 3 1 2 1 2 3 1 1 3 1
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
5 5 3 4 12 3 1 20 2 5 16 1 4 24 4 5 19
output:
58
result:
ok 1 number(s): "58"
Test #4:
score: 0
Accepted
time: 68ms
memory: 6732kb
input:
500 124750 1 2 31473 1 3 11597 1 4 6686 1 5 1214 1 6 14442 1 7 1042 1 8 19057 1 9 22648 1 10 24461 1 11 25714 1 12 3976 1 13 31954 1 14 7384 1 15 13988 1 16 28651 1 17 31599 1 18 8786 1 19 27068 1 20 9645 1 21 28281 1 22 11681 1 23 28897 1 24 31916 1 25 10462 1 26 23973 1 27 4615 1 28 5124 1 29 2026...
output:
8041745
result:
ok 1 number(s): "8041745"
Test #5:
score: 0
Accepted
time: 67ms
memory: 6832kb
input:
500 124750 1 2 3902 1 3 9006 1 4 2914 1 5 8753 1 6 2395 1 7 21406 1 8 14552 1 9 25834 1 10 28282 1 11 9684 1 12 11347 1 13 20545 1 14 16324 1 15 16951 1 16 11594 1 17 5035 1 18 17726 1 19 831 1 20 23194 1 21 7693 1 22 6147 1 23 315 1 24 32755 1 25 17078 1 26 11348 1 27 9587 1 28 21015 1 29 881 1 30 ...
output:
7803950
result:
ok 1 number(s): "7803950"
Test #6:
score: 0
Accepted
time: 454ms
memory: 14612kb
input:
100000 200000 82262 26109 1005476194 43106 86715 475153289 59086 60577 507254441 71498 80384 186530379 99676 3003 289537598 30772 72897 345346447 12686 87447 896623879 12520 27709 26442442 82734 20830 967590473 13380 76164 927495776 25723 55377 89078582 7173 86993 669894679 37790 94846 331905713 365...
output:
52538527353096
result:
ok 1 number(s): "52538527353096"
Test #7:
score: 0
Accepted
time: 455ms
memory: 14656kb
input:
100000 200000 15687 27598 177189307 20863 37114 1037884991 93538 8500 447584932 79876 73177 560212440 90266 81435 191658398 78954 69980 476724968 3024 95419 1016359891 28005 78423 806987047 22363 37592 995962252 80788 41407 484625454 32534 34520 497714826 66857 76961 49733398 2725 7116 786428563 393...
output:
52602853327156
result:
ok 1 number(s): "52602853327156"
Test #8:
score: 0
Accepted
time: 456ms
memory: 14772kb
input:
100000 200000 14517 31233 44615804 33486 41973 1052821004 49545 79689 319778876 8546 59914 211634618 54913 52423 157522220 7407 94892 619152362 68434 82081 302860551 79458 83213 51598667 36118 558 751409357 92878 62707 87357711 71932 57530 121862749 67177 75830 953279062 38483 37005 779602421 90440 ...
output:
52429947891248
result:
ok 1 number(s): "52429947891248"
Test #9:
score: 0
Accepted
time: 393ms
memory: 14752kb
input:
100000 200000 11656 60762 1 16805 66929 17 55148 55195 2 29841 9092 11 31848 48612 12 26261 82795 11 65162 78347 23 15597 88601 21 92692 7801 12 50087 67030 22 75497 23748 1 59304 62297 29 56011 68857 4 11540 9395 11 36408 13733 10 29267 965 15 45943 65984 29 6240 25729 29 64043 76902 7 78121 89050 ...
output:
1514667
result:
ok 1 number(s): "1514667"
Test #10:
score: 0
Accepted
time: 391ms
memory: 14900kb
input:
100000 200000 19078 1796 29 89160 3396 12 14155 57229 5 36362 16264 4 34378 35576 20 89020 76502 18 85772 59833 30 47358 3841 7 15219 48259 1 4778 42876 11 57340 52164 30 98346 7446 16 74577 91274 18 74128 7433 22 24777 57648 5 77806 76383 14 18741 73911 9 98620 83468 18 21676 45630 20 16077 32480 6...
output:
1515438
result:
ok 1 number(s): "1515438"
Test #11:
score: 0
Accepted
time: 90ms
memory: 9612kb
input:
100000 50000 1 2 1073741823 3 4 1073741823 5 6 1073741823 7 8 1073741823 9 10 1073741823 11 12 1073741823 13 14 1073741823 15 16 1073741823 17 18 1073741823 19 20 1073741823 21 22 1073741823 23 24 1073741823 25 26 1073741823 27 28 1073741823 29 30 1073741823 31 32 1073741823 33 34 1073741823 35 36 1...
output:
53687091150000
result:
ok 1 number(s): "53687091150000"
Test #12:
score: 0
Accepted
time: 82ms
memory: 10328kb
input:
100000 99999 2 1 1073741823 3 2 1073741823 4 3 1073741823 5 4 1073741823 6 5 1073741823 7 6 1073741823 8 7 1073741823 9 8 1073741823 10 9 1073741823 11 10 1073741823 12 11 1073741823 13 12 1073741823 14 13 1073741823 15 14 1073741823 16 15 1073741823 17 16 1073741823 18 17 1073741823 19 18 107374182...
output:
53687091150000
result:
ok 1 number(s): "53687091150000"
Test #13:
score: 0
Accepted
time: 22ms
memory: 10208kb
input:
100000 100000 2 1 1073741823 3 2 1073741823 4 3 1073741823 5 4 1073741823 6 5 1073741823 7 6 1073741823 8 7 1073741823 9 8 1073741823 10 9 1073741823 11 10 1073741823 12 11 1073741823 13 12 1073741823 14 13 1073741823 15 14 1073741823 16 15 1073741823 17 16 1073741823 18 17 1073741823 19 18 10737418...
output:
-1
result:
ok 1 number(s): "-1"
Test #14:
score: 0
Accepted
time: 93ms
memory: 5948kb
input:
100000 0
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
1 0
output:
0
result:
ok 1 number(s): "0"
Test #16:
score: 0
Accepted
time: 385ms
memory: 14728kb
input:
100000 200000 296 44153 0 5858 67253 0 77986 84024 0 13079 66431 0 48865 55236 0 53962 75116 0 74193 31717 0 4779 8496 0 91472 57204 0 96393 66037 0 26299 81546 0 66322 26724 0 74011 22225 0 79847 33417 0 32615 58874 0 49670 29377 0 44193 62155 0 51975 75204 0 33100 57873 0 3394 94539 0 86646 85744 ...
output:
0
result:
ok 1 number(s): "0"
Test #17:
score: 0
Accepted
time: 3ms
memory: 3940kb
input:
2000 1000 1488 921 0 772 1279 0 656 1845 0 602 1013 0 1967 1649 0 15 946 0 1983 775 0 1110 1254 0 1198 28 0 846 1721 0 1739 777 0 1675 225 0 315 1063 0 1156 46 0 430 1401 0 1105 812 0 1807 166 0 1808 1006 0 632 1396 0 1233 1928 0 1740 791 0 166 1713 0 1272 170 0 1365 790 0 792 1550 0 876 359 0 327 1...
output:
0
result:
ok 1 number(s): "0"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1 1 1 1 0
output:
0
result:
ok 1 number(s): "0"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
2 1 1 1 1
output:
-1
result:
ok 1 number(s): "-1"
Test #20:
score: 0
Accepted
time: 34ms
memory: 10428kb
input:
6500 192169 513 3871 8192 5819 4477 16 4415 3714 4096 4914 2493 32 3298 3772 256 5107 2443 0 27 114 0 958 798 524288 1488 5881 128 4023 1900 4096 1002 55 8388608 1784 3295 1 243 81 1048576 6333 1096 512 1673 2991 8192 1345 810 256 1755 1669 2097152 4470 1610 0 2030 1942 268435456 2970 3535 0 1528 14...
output:
-1
result:
ok 1 number(s): "-1"
Test #21:
score: 0
Accepted
time: 22ms
memory: 9572kb
input:
5000 147225 3872 3673 8192 4417 1256 16 564 4916 1024 3774 3013 2097152 115 16 0 105 959 4194304 4025 917 0 204 1002 262144 3296 1747 1048576 242 95 0 1636 2992 0 803 1345 65536 1112 1756 131072 2439 4471 0 1070 2031 67108864 3022 3536 0 1529 607 0 4728 3673 262144 3343 2291 8192 1269 135 524288 124...
output:
-1
result:
ok 1 number(s): "-1"
Test #22:
score: 0
Accepted
time: 5ms
memory: 4520kb
input:
1000 27940 566 561 512 315 270 0 320 177 0 513 120 16384 536 276 8388608 1 6 33562624 314 466 0 710 317 16384 105 115 0 173 960 512 380 38 0 84 403 16777216 722 410 0 136 422 0 243 230 0 663 843 0 561 788 32768 227 109 0 404 649 2 30 20 1 928 269 134217728 584 942 0 218 184 524288 302 417 2097152 38...
output:
-1
result:
ok 1 number(s): "-1"
Test #23:
score: 0
Accepted
time: 43ms
memory: 14752kb
input:
100000 199960 41459 56770 1 85904 40011 0 61166 64908 1 64605 72364 1 88723 98329 1 29588 55303 0 42294 75252 2 1192 53 1 9597 13382 1 608 86828 1 46783 59046 2 14022 310 0 11637 48162 0 2952 2186 1 96200 78489 2 31770 93593 0 43628 22964 1 19107 5707 0 25204 21480 2 65721 31640 0 29298 29234 0 5175...
output:
-1
result:
ok 1 number(s): "-1"
Test #24:
score: 0
Accepted
time: 35ms
memory: 11568kb
input:
20000 199537 9470 11393 256 972 17223 0 13022 6958 0 14513 11300 128 15072 19708 0 11100 507 0 15092 3699 0 68 260 1 72 2708 0 17407 16478 0 11849 1074 512 2836 881 512 2757 9671 512 559 615 2 1135 19283 0 18761 16209 0 1948 8763 64 946 3854 0 4687 5075 0 13185 2418 0 5895 1383 0 10389 8149 1 3787 4...
output:
-1
result:
ok 1 number(s): "-1"
Test #25:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
31 30 1 2 1 2 3 2 3 4 4 4 5 8 5 6 16 6 7 32 7 8 64 8 9 128 9 10 256 10 11 512 11 12 1024 12 13 2048 13 14 4096 14 15 8192 15 16 16384 16 17 32768 17 18 65536 18 19 131072 19 20 262144 20 21 524288 21 22 1048576 22 23 2097152 23 24 4194304 24 25 8388608 25 26 16777216 26 27 33554432 27 28 67108864 28...
output:
2147385345
result:
ok 1 number(s): "2147385345"
Test #26:
score: 0
Accepted
time: 24ms
memory: 5248kb
input:
30001 30000 1 2 1 2 3 2 3 4 4 4 5 8 5 6 16 6 7 32 7 8 64 8 9 128 9 10 256 10 11 512 11 12 1024 12 13 2048 13 14 4096 14 15 8192 15 16 16384 16 17 32768 17 18 65536 18 19 131072 19 20 262144 20 21 524288 21 22 1048576 22 23 2097152 23 24 4194304 24 25 8388608 25 26 16777216 26 27 33554432 27 28 67108...
output:
16106127345000
result:
ok 1 number(s): "16106127345000"
Test #27:
score: 0
Accepted
time: 81ms
memory: 10228kb
input:
100000 99999 1 2 1 2 3 2 3 4 4 4 5 8 5 6 16 6 7 32 7 8 64 8 9 128 9 10 256 10 11 512 11 12 1024 12 13 2048 13 14 4096 14 15 8192 15 16 16384 16 17 32768 17 18 65536 18 19 131072 19 20 262144 20 21 524288 21 22 1048576 22 23 2097152 23 24 4194304 24 25 8388608 25 26 16777216 26 27 33554432 27 28 6710...
output:
53677425377466
result:
ok 1 number(s): "53677425377466"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
100 99 1 2 0 2 3 0 3 4 0 4 5 1073741823 5 6 1073741823 6 7 0 7 8 0 8 9 0 9 10 1073741823 10 11 1073741823 11 12 0 12 13 0 13 14 0 14 15 1073741823 15 16 1073741823 16 17 0 17 18 0 18 19 0 19 20 1073741823 20 21 1073741823 21 22 0 22 23 0 23 24 0 24 25 1073741823 25 26 1073741823 26 27 0 27 28 0 28 2...
output:
21474836460
result:
ok 1 number(s): "21474836460"
Test #29:
score: 0
Accepted
time: 75ms
memory: 10168kb
input:
100000 99999 1 2 0 2 3 0 3 4 0 4 5 1073741823 5 6 1073741823 6 7 0 7 8 0 8 9 0 9 10 1073741823 10 11 1073741823 11 12 0 12 13 0 13 14 0 14 15 1073741823 15 16 1073741823 16 17 0 17 18 0 18 19 0 19 20 1073741823 20 21 1073741823 21 22 0 22 23 0 23 24 0 24 25 1073741823 25 26 1073741823 26 27 0 27 28 ...
output:
21474836460000
result:
ok 1 number(s): "21474836460000"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
5 5 4 5 0 5 3 2 2 1 2 4 3 1 2 3 2
output:
-1
result:
ok 1 number(s): "-1"
Test #31:
score: 0
Accepted
time: 40ms
memory: 14456kb
input:
100000 200000 79390 14339 1062014775 10711 22137 642501688 19927 91260 724640129 59374 58304 185585315 10009 3125 929476576 97161 16637 1007223371 65315 99616 940307862 84142 93534 808942465 90345 24806 836853171 73468 98591 292252796 12881 87100 878527586 8440 109 371863064 44492 77430 42369294 849...
output:
-1
result:
ok 1 number(s): "-1"
Test #32:
score: 0
Accepted
time: 432ms
memory: 14088kb
input:
100000 200000 6288 46963 885386162 60135 32093 1072538756 20841 90806 589855509 88761 13902 920623297 11960 54333 393725401 11960 54333 393725401 72721 1581 3526173 72721 1581 3526173 69751 2337 936474097 31545 89078 1549380 12049 82108 370330402 12049 82108 370330402 32081 84594 513288083 10047 558...
output:
49270598583476
result:
ok 1 number(s): "49270598583476"
Test #33:
score: 0
Accepted
time: 388ms
memory: 14636kb
input:
100000 200000 12323 19855 16777344 97632 10250 0 89270 53844 1048584 47507 21539 8388608 11762 66212 570425344 40891 5028 2048 13352 59961 16386 20907 58079 0 44969 65900 4096 57089 72513 160 29044 53982 0 65137 56186 0 89184 80135 0 29473 66752 0 99953 52357 2048 93623 56188 81920 53764 10802 67108...
output:
2141391761458
result:
ok 1 number(s): "2141391761458"
Test #34:
score: 0
Accepted
time: 400ms
memory: 14824kb
input:
100000 200000 7262 1663 134742016 60091 75297 168034304 65150 91330 3146888 4617 31411 100801024 90213 20118 33587200 75642 85822 580 30333 69858 2048 9207 23149 3 45835 17029 64 47608 54511 302514816 77127 57214 134217730 26246 45661 581632 99696 64721 73728000 34885 65238 67109384 99061 83082 2684...
output:
5268363507189
result:
ok 1 number(s): "5268363507189"
Test #35:
score: 0
Accepted
time: 112ms
memory: 10540kb
input:
632 199396 1 2 973410658 1 3 169156354 1 4 176442683 1 5 38345635 1 6 139278818 1 7 134552866 1 8 713234442 1 9 169941286 1 10 203426610 1 11 252451074 1 12 191172914 1 13 168130852 1 14 707042082 1 15 100686154 1 16 134285354 1 17 184945190 1 18 675354690 1 19 184884615 1 20 170072357 1 21 70969577...
output:
136422868344
result:
ok 1 number(s): "136422868344"
Test #36:
score: 0
Accepted
time: 406ms
memory: 14792kb
input:
100000 200000 72392 82989 9 45333 78560 2361344 32408 36239 131072 83422 30623 150999169 92500 77378 36 95014 55108 1049600 34391 91926 16811076 49661 59671 2097152 17427 96594 272663040 90066 63898 4194304 5634 80005 134217728 4183 84658 268435456 8420 45530 128 90832 35008 33555472 47948 16484 805...
output:
6968424867729
result:
ok 1 number(s): "6968424867729"
Test #37:
score: 0
Accepted
time: 380ms
memory: 15212kb
input:
100000 200000 65097 83979 0 4153 56517 1081344 30506 34075 2097664 64896 89019 71320576 92259 84363 1049601 72127 46037 64 88543 87982 8392960 13806 38151 536938496 13776 91398 134217734 60382 61381 2113536 87001 46048 8388640 10698 40674 50332832 9928 4407 4096 4935 30357 268697634 58104 95352 6710...
output:
3467156282964
result:
ok 1 number(s): "3467156282964"