QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#37694#1168. Find the XORFroggyguaWA 89ms17800kbC++171.1kb2022-07-02 15:20:552022-07-02 15:20:58

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-02 15:20:58]
  • Judged
  • Verdict: WA
  • Time: 89ms
  • Memory: 17800kb
  • [2022-07-02 15:20:55]
  • Submitted

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'