QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#191519#7524. A Challenge For a TouristDays_of_Future_Past#TL 8ms20312kbC++232.3kb2023-09-30 00:28:442023-09-30 00:28:44

Judging History

你现在查看的是最新测评结果

  • [2023-09-30 00:28:44]
  • 评测
  • 测评结果:TL
  • 用时:8ms
  • 内存:20312kb
  • [2023-09-30 00:28:44]
  • 提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define per(i,n) for(int i=n;i>=1;--i)
#define pb push_back
#define mp make_pair
#define N 210000
struct xorbase {
	int a[30];
	bool ins(int w) {
		for(int i = 29;i >= 0;--i) {
			if(w >> i & 1) {
				if(a[i]) {
					w ^= a[i];
				} else {
					a[i] = w;
					return 1;
				}
			}
		}
		return 0;
	}
	bool test(int w) {
		for(int i = 29;i >= 0;--i) if(w >> i & 1) {
			w ^= a[i];
		}
		return w == 0;
	}
} T[N];
int n,m,q;
struct Edge
{
	int x,y,w;
	friend bool operator <(Edge x,Edge y)
	{
		return x.w<y.w;
	}
}edge[N];

struct Query
{
	int x,y,h,id;
};
vector<Query> Q[N],QQ[N];
map<int,int> first,last;
int ans[N],v[N];
int father[N],sum[N];
int getfather(int x)
{
	if (x==father[x])return x;
	int ret=getfather(father[x]);
	sum[x]^=sum[father[x]];
	return father[x]=ret;
}
void ask(Query x,int w)
{
	if (ans[x.id]!=-1)return;
	int t1=getfather(x.x);
	int t2=getfather(x.y);
	if (t1!=t2)return;
	if (T[t1].test(sum[x.x]^sum[x.y]^x.h))ans[x.id]=w;
}
int main()
{
	cin>>n>>m;
	rep(i,m)scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w);
	sort(edge+1,edge+m+1);
	rep(i,n)father[i]=i;
	cin>>q;
	rep(i,q)
	{
		int x,y,h;
		scanf("%d%d%d",&x,&y,&h);
		Q[x].pb((Query){x,y,h,i});
		Q[y].pb((Query){x,y,h,i});
	}
	rep(i,q)ans[i]=-1;
	
	for(auto ee:edge)
	{
		int x=ee.x,y=ee.y,w=ee.w;
		int t1=getfather(x);
		int t2=getfather(y);
		if(t1==t2) 
		{
			T[t1].ins(w^sum[x]^sum[y]);
			for(auto p:QQ[t1])ask(p,w);
			continue;
		}
		//t1!=t2, not the same component
		//merge t1 -> t2
		if(Q[t1].size()>Q[t2].size())swap(t1,t2),swap(x,y);
		for(auto p:QQ[t1])QQ[t2].pb(p);
		for(auto p:Q[t1])Q[t2].pb(p);
		father[t1]=t2;
		sum[t1]=sum[x]^sum[y]^w;

		for(int i=0;i<=29;i++)
			if (T[t1].a[i])
				T[t2].ins(T[t1].a[i]);
		for(auto p:QQ[t2])ask(p,w);
		for(auto p:QQ[t1])ask(p,w);
		for(auto p:Q[t1]) {
			if(!v[p.id])
				if (getfather(p.x)==getfather((p.y)))
				{
					v[p.id] = 1;
					QQ[t2].push_back(p);
					ask(p,w);
				}
		}
	}

	rep(i,q)printf("%d\n",ans[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 20204kb

input:

6 6
5 6 3
6 2 2
1 2 1
2 3 2
2 4 3
4 5 4
3
1 3 1
1 3 3
1 3 5

output:

-1
2
4

result:

ok 3 number(s): "-1 2 4"

Test #2:

score: 0
Accepted
time: 4ms
memory: 18288kb

input:

2 1
1 2 1
1
1 2 1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 4ms
memory: 20208kb

input:

5 10
1 2 4
2 2 0
1 1 7
2 1 7
4 1 1
5 5 1
4 1 4
5 2 6
1 1 2
2 4 7
10
1 4 3
1 2 5
3 2 1
3 5 5
2 4 0
3 2 0
2 1 2
2 3 6
5 1 7
2 3 3

output:

2
6
-1
-1
4
-1
6
-1
6
-1

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 8ms
memory: 18264kb

input:

10 20
3 5 667
2 5 71
2 9 47
7 9 941
9 1 564
2 1 892
7 1 627
2 2 989
8 9 978
1 3 936
1 1 807
8 4 564
6 9 518
5 4 896
2 9 607
3 9 453
1 3 402
10 8 935
7 3 826
1 6 707
40
3 10 164
2 10 248
5 6 708
5 9 764
1 9 711
3 8 377
9 1 640
7 1 554
3 1 504
4 9 761
1 8 111
5 8 296
4 2 97
10 4 896
5 1 232
5 8 154
7 ...

output:

-1
941
-1
-1
-1
941
941
936
892
-1
896
-1
896
-1
-1
896
-1
941
-1
936
936
936
941
941
892
-1
-1
941
826
-1
896
-1
-1
936
896
-1
941
941
941
941

result:

ok 40 numbers

Test #5:

score: 0
Accepted
time: 4ms
memory: 18308kb

input:

20 40
11 3 622
15 1 463
1 13 754
10 16 87
17 16 602
19 4 1003
4 5 50
1 12 598
13 11 600
8 12 26
8 3 325
18 17 329
9 15 961
12 6 110
8 12 756
8 6 415
19 11 159
8 6 595
6 6 32
10 15 573
18 9 659
2 16 685
11 15 881
10 11 614
20 8 941
12 17 473
12 20 796
17 12 881
13 4 870
5 1 76
19 3 191
17 8 698
7 20 ...

output:

685
796
685
659
614
622
796
685
615
685
622
-1
-1
622
622
622
622
796
685
614
622
622
796
602
685
615
615
796
-1
622
796
685
659
614
685
659
614
685
685
685
685
659
-1
685
685
685
685
796
685
685
-1
685
598
796
685
796
796
622
-1
685
685
622
685
622
622
615
622
685
-1
-1
-1
685
796
615
615
796
685
7...

result:

ok 80 numbers

Test #6:

score: 0
Accepted
time: 4ms
memory: 20292kb

input:

30 60
20 6 610
28 8 847
1 9 442
30 5 574
5 23 49
12 17 415
3 24 116
3 22 164
3 16 464
27 1 179
19 11 689
16 8 840
12 28 242
13 14 300
20 21 243
6 7 50
10 28 207
27 2 858
5 17 164
27 19 839
28 25 399
10 11 185
6 10 157
24 8 309
2 22 722
5 4 688
13 19 314
10 15 858
13 22 286
12 24 376
29 17 37
7 4 762...

output:

526
513
513
513
464
526
442
513
526
513
526
526
526
526
513
376
513
526
526
526
513
513
526
513
498
526
464
526
498
394
526
526
526
526
526
526
498
526
526
526
526
526
526
526
442
498
526
513
526
526
513
526
513
526
513
526
513
513
513
376
526
442
513
513
513
415
464
415
498
513
526
498
498
464
513
...

result:

ok 120 numbers

Test #7:

score: 0
Accepted
time: 4ms
memory: 18272kb

input:

40 80
12 19 34
3 23 7
2 6 779
20 14 464
14 38 950
39 1 46
14 13 18
17 16 736
4 35 816
9 13 507
27 38 18
1 3 905
29 9 628
3 32 740
37 3 410
23 33 428
19 8 69
38 34 501
35 31 446
9 7 831
34 21 33
14 7 133
9 24 545
18 9 247
20 6 10
19 24 176
4 30 780
14 15 108
1 10 263
17 38 748
38 2 894
36 28 556
2 7 ...

output:

556
545
412
-1
-1
464
545
556
464
545
464
556
-1
295
545
424
556
545
545
365
464
545
556
556
412
556
412
464
464
556
545
464
545
464
-1
556
556
464
464
424
-1
410
-1
-1
-1
556
545
295
464
545
556
412
464
545
464
545
-1
545
-1
295
545
545
464
545
-1
545
-1
556
558
410
-1
464
545
464
464
-1
-1
424
-1
...

result:

ok 160 numbers

Test #8:

score: 0
Accepted
time: 4ms
memory: 18184kb

input:

50 100
33 19 845
50 31 685
27 25 461
15 36 18
17 35 853
49 32 539
7 6 840
24 8 1013
26 31 438
25 29 943
7 17 547
9 4 976
43 50 94
10 23 938
46 47 649
13 6 894
42 20 854
16 27 51
17 4 690
6 18 456
37 8 44
12 35 681
18 43 306
47 24 882
38 46 91
27 29 998
13 22 894
31 18 1010
42 27 165
9 2 75
6 19 588
...

output:

512
674
-1
701
544
541
572
572
572
674
572
572
541
572
544
544
544
588
853
572
572
572
572
572
572
539
572
572
572
544
-1
572
541
572
544
572
572
541
572
674
544
588
588
544
588
544
572
853
572
507
572
674
714
674
572
714
853
732
572
732
572
512
588
541
544
572
544
714
572
572
-1
853
541
544
541
572...

result:

ok 200 numbers

Test #9:

score: 0
Accepted
time: 4ms
memory: 20312kb

input:

60 120
34 41 6
4 31 444
54 5 918
58 8 474
6 44 453
43 52 497
43 59 354
25 40 189
26 23 273
19 42 977
6 1 296
55 56 716
22 21 116
22 46 392
52 7 103
10 26 502
60 39 358
14 20 646
48 4 772
17 29 759
11 40 781
3 8 637
21 46 886
28 21 181
7 48 425
36 40 2
43 33 803
59 21 859
36 28 548
4 9 951
57 13 170
...

output:

525
611
386
-1
524
679
562
474
611
525
386
525
-1
951
735
386
611
358
591
386
425
340
764
524
524
918
591
386
525
764
524
524
525
524
524
525
611
951
524
524
524
951
524
735
386
918
591
951
525
386
524
525
-1
348
764
524
951
524
524
524
-1
764
386
525
759
340
951
679
759
951
386
524
524
716
358
524
...

result:

ok 240 numbers

Test #10:

score: 0
Accepted
time: 4ms
memory: 18292kb

input:

70 140
14 56 377
66 1 557
34 54 500
21 55 342
70 3 452
21 16 1004
37 59 623
54 39 1001
32 32 964
63 59 208
57 7 785
46 24 324
23 39 724
9 54 482
21 21 734
54 46 197
19 56 222
63 45 731
6 18 56
7 33 582
10 68 40
29 18 276
3 32 651
25 43 920
47 6 404
39 62 946
56 49 839
35 57 168
2 49 367
12 6 442
42 ...

output:

594
539
539
539
635
450
539
472
490
539
525
594
539
539
543
539
539
920
539
696
582
472
472
539
450
594
539
573
543
573
649
472
594
490
573
539
539
464
543
450
519
472
635
539
453
539
472
519
472
543
525
539
450
644
644
482
696
594
635
444
539
644
539
543
412
920
594
519
453
539
594
490
519
450
539
...

result:

ok 280 numbers

Test #11:

score: 0
Accepted
time: 2ms
memory: 20224kb

input:

80 160
29 67 324
31 48 232
75 20 778
18 21 597
49 39 197
42 77 854
29 70 689
45 22 63
10 4 782
27 28 141
5 71 626
23 9 151
37 62 844
63 19 984
44 80 982
68 9 99
75 62 138
41 32 230
20 13 611
35 71 916
47 26 436
45 73 748
30 75 64
29 9 861
17 8 840
59 73 230
17 6 204
75 59 608
47 41 444
43 79 703
63 ...

output:

844
515
664
603
448
664
953
515
515
626
515
515
603
953
515
844
515
515
508
935
459
635
515
448
736
-1
515
576
448
844
515
878
515
576
576
-1
576
664
501
459
501
515
515
664
626
736
515
515
501
953
501
501
515
703
635
523
635
515
664
501
459
626
576
703
935
878
603
635
844
515
515
501
783
454
523
50...

result:

ok 320 numbers

Test #12:

score: 0
Accepted
time: 8ms
memory: 20272kb

input:

90 180
82 2 648
85 65 932
10 78 136
48 6 670
69 21 697
55 50 763
71 60 455
62 20 665
74 12 173
89 27 750
19 38 83
47 24 152
66 73 370
84 22 941
6 12 571
74 37 568
20 37 954
5 74 998
86 48 986
29 64 32
53 57 693
9 73 69
39 49 765
32 45 997
49 50 543
51 46 790
65 87 255
50 65 480
23 87 732
27 35 220
1...

output:

699
514
568
514
514
720
568
648
648
665
699
480
665
528
528
464
514
948
699
461
699
514
720
528
600
871
528
600
699
571
611
514
790
871
528
665
514
1021
720
492
790
699
720
480
699
597
528
665
528
699
528
568
514
528
699
1021
571
699
699
568
699
514
568
568
599
492
790
528
528
528
699
568
720
514
61...

result:

ok 360 numbers

Test #13:

score: 0
Accepted
time: 3ms
memory: 20272kb

input:

100 200
6 45 162
46 33 419
18 88 669
75 4 966
64 3 262
66 35 479
30 76 952
20 80 734
28 48 51
28 64 307
46 24 566
23 89 429
14 66 609
73 15 344
81 82 880
100 67 724
60 14 596
98 17 417
32 24 731
72 12 163
70 66 216
8 7 852
43 16 776
100 75 760
39 18 726
6 66 278
45 71 691
84 58 1011
58 88 892
28 71 ...

output:

528
514
720
609
581
429
468
514
528
528
528
429
528
552
528
479
514
691
514
517
585
514
585
806
585
528
585
434
528
514
528
514
528
720
552
552
609
528
514
528
528
479
528
517
344
514
417
528
609
528
446
806
806
528
528
-1
550
434
806
691
550
528
806
609
528
479
552
514
552
528
806
514
514
-1
514
60...

result:

ok 400 numbers

Test #14:

score: -100
Time Limit Exceeded

input:

200000 200000
109342 177585 227729360
47204 185227 65000004
18413 107067 731586911
193618 193271 176899956
193975 45521 123073233
21309 181614 329804012
138160 118319 203452859
124884 8693 566070106
159912 46179 902860088
166651 68050 474901516
186453 75667 211242475
128492 19333 1063841125
15161 12...

output:


result: