QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#191519 | #7524. A Challenge For a Tourist | Days_of_Future_Past# | TL | 8ms | 20312kb | C++23 | 2.3kb | 2023-09-30 00:28:44 | 2023-09-30 00:28:44 |
Judging History
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...