QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#37694 | #1168. Find the XOR | Froggygua | WA | 89ms | 17800kb | C++17 | 1.1kb | 2022-07-02 15:20:55 | 2022-07-02 15:20:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 100020
typedef long long ll;
vector<pair<int,int> > G[N];
int n,m,Q;
class Basis{
public:
int d[32];
void Insert(int x){
for(int i=29;i>=0;--i){
if(x>>i&1){
if(!d[i]){
d[i]=x;
for(int j=i+1;j<30;++j){
if(d[j]>>i&1){
d[j]^=x;
}
}
return;
}
else{
x^=d[i];
}
}
}
}
}B;
int dfn[N],dis[N],num,sxor[N];
void dfs(int u){
dfn[u]=++num;
for(auto [v,w]:G[u]){
if(!dfn[v]){
dis[v]=dis[u]^w;
dfs(v);
}
else if(dfn[u]>=dfn[v]){
B.Insert(dis[u]^dis[v]^w);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>Q;
for(int i=1;i<=m;++i){
int u,v,w;
cin>>u>>v>>w;
G[u].emplace_back(v,w);
G[v].emplace_back(u,w);
}
dfs(1);
for(int i=1;i<=n;++i){
sxor[i]=sxor[i-1]^dis[i];
}
while(Q--){
int l,r;
cin>>l>>r;
int len=r-l+1;
int w=sxor[r]^sxor[l-1];
if(len&1)w=0;
int ans=w;
int t=(1LL*(r-l)*(r-l+1)/2)&1;
for(int i=29;i>=0;--i){
if((w>>i&1)!=t){
ans^=B.d[i];
}
}
cout<<ans<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 5924kb
input:
8 10 7 1 2 662784558 3 2 195868257 3 4 294212653 4 5 299265014 6 5 72652580 6 7 29303370 7 8 183954825 2 1 752722885 5 3 197591314 8 4 877461873 4 8 5 7 6 7 2 3 7 8 3 4 2 7
output:
0 713437792 738051848 716356296 736682272 1003204975 987493236
result:
ok 7 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 5928kb
input:
2 1 1 1 2 31 1 2
output:
31
result:
ok 1 number(s): "31"
Test #3:
score: 0
Accepted
time: 3ms
memory: 6404kb
input:
2 3 1 1 2 71 1 1 86 2 2 48 1 2
output:
119
result:
ok 1 number(s): "119"
Test #4:
score: 0
Accepted
time: 28ms
memory: 7000kb
input:
500 700 100000 2 1 147383090 2 3 981594190 3 4 948414594 5 4 739739766 6 5 586581109 6 7 418429007 8 7 852078976 8 9 233093009 9 10 712947390 10 11 130658520 12 11 332650604 12 13 52607525 14 13 260905070 14 15 962878811 16 15 195610313 16 17 303149251 18 17 140878375 19 18 338952072 20 19 105254306...
output:
276955137 0 0 0 255950049 276955137 276955137 276955137 80874004 276955137 0 276955137 888035320 0 488872381 804414943 276955137 0 620785200 26674723 923328495 0 276955137 354542402 0 0 276955137 0 0 65166720 26464393 605344613 200770908 705353995 276955137 549239290 1041115160 0 276955137 276955137...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 25ms
memory: 6592kb
input:
500 700 100000 2 1 147383090 3 1 502825032 2 4 739739766 5 4 924173383 5 6 852078976 7 3 155380968 8 1 130658520 9 6 790080077 1 10 260905070 4 11 501238476 3 12 303149251 1 13 829675709 14 13 1052543062 15 10 218467971 11 16 640919377 17 2 338021594 8 18 480588661 19 18 481230688 5 20 305467460 20 ...
output:
1072557464 200285858 38794233 0 0 288837123 59655647 88049516 0 860362443 0 288837123 263423587 272302874 288837123 288837123 288837123 288837123 288837123 564055414 288837123 366562468 288837123 288837123 288837123 300993538 288837123 87399008 953617005 62945233 0 288837123 0 0 776022391 0 91616542...
result:
ok 100000 numbers
Test #6:
score: 0
Accepted
time: 65ms
memory: 17604kb
input:
80000 100000 100000 2 1 1023327746 2 3 818417961 4 3 126848850 4 5 51064172 5 6 1000986215 6 7 59810073 8 7 798687333 9 8 74142106 10 9 244018456 11 10 712187193 11 12 507813741 13 12 829264806 13 14 408747511 15 14 711278199 16 15 669721451 17 16 896629155 17 18 522370852 18 19 510712839 19 20 4174...
output:
16975875 492539713 0 798868339 0 460216450 437620332 877769772 16975875 16975875 16975875 16975875 761853197 0 16975875 140076428 16975875 154801232 37537178 203814401 16975875 0 0 0 16975875 445505456 16975875 127167896 0 99025153 948984548 989337155 378174839 0 581314797 593215150 0 254760207 2801...
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 89ms
memory: 12572kb
input:
80000 100000 100000 1 2 1023327746 1 3 1057663656 2 4 51064172 5 2 155368044 6 1 798687333 3 7 362026831 6 8 712187193 7 9 367376168 9 10 408747511 2 11 222355293 12 6 896629155 13 8 1029080248 13 14 41747872 3 15 259809647 16 15 435682136 17 2 27782510 7 18 164081197 3 19 483763432 15 20 245587365 ...
output:
0 905343599 1014100949 200990880 804583005 0 0 0 940679401 0 236276845 538976513 538976513 0 0 538976513 0 289588480 751252155 0 0 538976513 0 945025329 538976513 538976513 0 0 538976513 538976513 538976513 538976513 853246624 0 0 0 0 538976513 0 0 51340978 308913573 0 461768125 280027106 875271057 ...
result:
ok 100000 numbers
Test #8:
score: 0
Accepted
time: 27ms
memory: 7196kb
input:
500 700 100000 1 2 1041334872 3 2 337520775 4 3 642386166 4 5 477271852 6 5 408924980 7 6 1006511760 8 7 764443757 8 9 337160471 10 9 57685166 11 10 615243034 11 12 532865851 12 13 641824613 13 14 793835787 14 15 584580537 15 16 924799815 17 16 831025483 18 17 313855439 19 18 809945411 19 20 8972843...
output:
476577143 41052745 708606633 476577143 476577143 12715302 186461343 476577143 160978326 476577143 476577143 476577143 174480316 877234345 476577143 0 476577143 1007088507 476577143 0 476577143 600690706 375218346 484909352 476577143 0 476577143 476577143 0 0 546757520 736724974 0 23114918 1016180820...
result:
ok 100000 numbers
Test #9:
score: 0
Accepted
time: 27ms
memory: 6352kb
input:
500 700 100000 1 2 1041334872 1 3 302927383 4 3 477271852 1 5 220538337 3 6 764443757 1 7 760776106 3 8 615243034 9 6 1038314958 5 10 793835787 11 10 1002327750 4 12 831025483 12 13 10605223 14 1 89728437 15 4 895757784 7 16 13787085 5 17 277762836 18 13 552650465 7 19 172467872 9 20 199743841 21 9 ...
output:
927609549 260079298 982797257 1022191178 0 0 0 982797257 862302367 148973018 982797257 209719276 0 71229656 982797257 982797257 982797257 92448581 47803701 0 40270145 17984192 0 1020435735 0 982797257 49297898 0 130671173 0 65400153 164248789 982797257 982797257 982797257 238787564 32756917 98279725...
result:
ok 100000 numbers
Test #10:
score: 0
Accepted
time: 74ms
memory: 17800kb
input:
80000 100000 100000 2 1 843537703 3 2 174344546 3 4 894562246 5 4 862338082 5 6 823330086 7 6 647892827 8 7 711052114 8 9 178209568 10 9 662498057 11 10 123029882 12 11 708028988 12 13 344740071 13 14 941678228 15 14 332979926 15 16 325169129 16 17 350763564 17 18 695347916 18 19 981706177 20 19 152...
output:
533086881 1045498625 498396009 0 0 118058719 93544793 492821731 632050461 0 422590356 0 533086881 635019788 0 91860395 636442392 0 533086881 533086881 65477526 515006793 480782585 0 0 0 533086881 0 667777744 0 533086881 533086881 533086881 573289648 533086881 0 1059028994 996254507 88483393 97461678...
result:
ok 100000 numbers
Test #11:
score: 0
Accepted
time: 88ms
memory: 12604kb
input:
80000 100000 100000 2 1 843537703 3 1 857766007 4 2 862338082 4 5 525474822 6 5 711052114 6 7 967421970 8 2 123029882 9 8 615611049 10 3 941678228 11 2 723444567 12 7 350763564 13 10 210009762 14 9 152675070 4 15 937099460 16 2 882291667 5 17 1041265576 13 18 236143001 19 9 175000616 20 12 139863746...
output:
423858191 0 0 0 1028675370 577892613 1025000493 110438709 0 824371872 992665401 0 705152963 106169312 487796537 0 423858191 0 0 749214703 580600918 36127068 0 710983203 0 423858191 0 859760688 430689905 0 0 645701419 423858191 830788865 0 739322377 1067604331 453698414 536579490 539857281 0 0 867122...
result:
ok 100000 numbers
Test #12:
score: 0
Accepted
time: 26ms
memory: 6032kb
input:
500 700 100000 1 2 861544829 2 3 767189184 4 3 336357738 4 5 214803939 6 5 231268852 6 7 520852689 8 7 676808538 8 9 441227933 10 9 476164767 11 10 26085723 12 11 733081099 13 12 157299877 13 14 253024680 14 15 206282263 16 15 580247493 16 17 285159891 18 17 486832503 19 18 207196926 20 19 200655635...
output:
0 14461927 940604994 940604994 0 940604994 940604994 974830766 0 76532912 0 940604994 940604994 940604994 40162731 1034299828 101949713 1010150691 940604994 359062 21655942 96483989 940604994 0 71048495 1016282729 0 125662024 940604994 0 129767497 1037705572 950432668 1049173911 940604994 940604994 ...
result:
ok 100000 numbers
Test #13:
score: -100
Wrong Answer
time: 35ms
memory: 6936kb
input:
500 700 100000 2 1 861544829 1 3 103029734 4 2 214803939 5 2 590645115 5 6 676808538 6 7 292429420 6 8 26085723 6 9 212808015 8 10 253024680 8 11 429675200 5 12 285159891 11 13 265276561 1 14 200655635 3 15 499305773 8 16 460396617 8 17 217504078 18 12 624712269 17 19 937446880 20 6 94020222 6 21 82...
output:
0 558419987 0 0 777360118 0 170551813 0 0 275670217 0 1054350648 170551813 610037996 170551813 791041459 170551813 773176904 170551813 991904358 0 528051839 506490081 343681526 170551813 170551813 170551813 533875428 29073293 174208665 813188469 170551813 0 170551813 1056829165 980034347 286541553 1...
result:
wrong answer 5th numbers differ - expected: '779463378', found: '777360118'