QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#35164 | #877. Company At Danger | AutumnKite | AC ✓ | 99ms | 3804kb | C++17 | 1.4kb | 2022-06-14 10:15:14 | 2022-06-14 10:15:16 |
Judging History
answer
#include <bits/stdc++.h>
class basis {
int n;
std::vector<long long> a;
public:
basis(int l) : n(l), a(n) {}
void insert(long long x) {
for (int i = n - 1; i >= 0; --i) {
if (x >> i & 1) {
if (!a[i]) {
a[i] = x;
return;
}
x ^= a[i];
}
}
}
long long query(long long x) const {
for (int i = n - 1; i >= 0; --i) {
if (x >> i & 1 && a[i]) {
x ^= a[i];
}
}
return x;
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, q;
std::cin >> n >> m >> q;
std::vector<int> fa(n);
std::vector<long long> fw(n);
std::iota(fa.begin(), fa.end(), 0);
basis B(60);
std::function<int(int)> find = [&](int x) {
if (fa[x] == x) {
return x;
}
int fx = find(fa[x]);
fw[x] ^= fw[fa[x]];
return fa[x] = fx;
};
auto merge = [&](int x, int y, long long w) {
int fx = find(x), fy = find(y);
w ^= fw[x] ^ fw[y];
if (fx == fy) {
B.insert(w);
return;
}
fa[fy] = fx;
fw[fy] = w;
};
for (int i = 0; i < m; ++i) {
int u, v;
long long w;
std::cin >> u >> v >> w;
--u, --v;
merge(u, v, w);
}
while (q--) {
int u, v;
std::cin >> u >> v;
--u, --v;
find(u), find(v);
std::cout << B.query(fw[u] ^ fw[v]) << "\n";
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3652kb
input:
3 3 3 1 2 2 1 3 2 2 3 3 1 2 1 3 2 3
output:
1 1 0
result:
ok 3 number(s): "1 1 0"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3672kb
input:
7 10 5 1 2 45 2 3 11 2 4 46 3 4 28 3 5 59 3 6 12 3 7 3 4 5 11 5 6 23 6 7 20 1 4 2 6 3 5 1 7 5 5
output:
1 5 0 5 0
result:
ok 5 number(s): "1 5 0 5 0"
Test #3:
score: 0
Accepted
time: 31ms
memory: 3740kb
input:
10000 60059 25000 5140 602 0 5140 4077 546574455686537395 4077 602 546574455686537394 5140 5492 401628381435124761 5492 602 401628381435124763 5140 4907 231352666654267087 4907 602 231352666654267083 5140 9430 281314177097774626 9430 602 281314177097774634 5140 6477 63541404444272256 6477 602 635414...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 25000 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
3 3 1 1 2 1125899906842624 2 3 2251799813685248 1 3 4503599627370496 1 3
output:
3377699720527872
result:
ok 1 number(s): "3377699720527872"
Test #5:
score: 0
Accepted
time: 90ms
memory: 3564kb
input:
447 99681 100000 1 2 839629476433734568 1 3 845110558248768075 2 3 5663371925419393 1 4 666311649684467955 2 4 857093696697375108 3 4 175625954325234025 1 5 730513119983838617 2 5 271241040987860966 3 5 926850784105132545 4 5 160225824853823399 1 6 868417719633989649 2 6 764747536929294306 3 6 83083...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #6:
score: 0
Accepted
time: 99ms
memory: 3608kb
input:
447 99681 100000 1 2 627663192746874475 1 3 19290296808425098 2 3 535230885919825297 1 4 280005753405749329 2 4 144817693805159423 3 4 547893093723790405 1 5 983798244028161326 2 5 452001949454517034 3 5 476691542611604051 4 5 246803527590805080 1 6 661688860768044487 2 6 479581632501668330 3 6 1150...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 97ms
memory: 3636kb
input:
447 99681 100000 1 2 459262317331420345 1 3 678578424260523280 2 3 919157960914439115 1 4 575813309612474940 2 4 656630762923569948 3 4 310576199693424847 1 5 338661015506182358 2 5 610398178771320796 3 5 87279645314970985 4 5 72033289514449248 1 6 901513851104134986 2 6 531402731999006616 3 6 12358...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #8:
score: 0
Accepted
time: 88ms
memory: 3660kb
input:
10000 100000 100000 904 3440 0 3440 6263 0 3440 4110 0 3440 1695 0 4110 1750 0 6263 6248 0 3440 5515 0 4110 4907 0 1750 9728 0 9728 475 61939206189494465 1750 7950 61939206189494465 475 3656 0 9728 7931 61939206189494465 4907 2894 61939206189494465 4907 8182 61939206189494465 4907 1508 6193920618949...
output:
157337146822428505 346888250740471042 316054772220987195 273059701717781813 134073400838292992 248610710111036325 61354361280277806 66464699198964244 177166870307382543 561247121067855434 465390246790713402 569390866580846397 192105177033788233 333250167758388269 481521854993772524 49558026233245587...
result:
ok 100000 numbers
Test #9:
score: 0
Accepted
time: 9ms
memory: 3560kb
input:
1000 10000 10000 163 313 0 163 618 0 618 260 0 260 2 0 618 229 0 163 865 0 260 984 0 163 816 0 313 235 0 2 217 0 313 108 0 229 421 0 816 605 0 816 543 0 229 134 0 260 368 0 108 650 0 368 102 0 984 708 0 108 754 0 708 464 0 754 207 0 605 470 0 605 771 0 163 208 0 421 454 0 605 152 0 134 26 0 108 157 ...
output:
425235912297974419 111295915873857227 117630609816836199 1192914893482556 536492597487056833 471879764810016183 0 425235912297974419 0 30609785862386534 425235912297974419 1192914893482556 11979596371375788 11979596371375788 367812452785616362 329286628262320929 329286628262320929 107173499716195301...
result:
ok 10000 numbers
Test #10:
score: 0
Accepted
time: 56ms
memory: 3640kb
input:
8319 29055 100000 2 1 6244459242977867 3 2 20320163049928538 4 1 33881361444287230 5 4 23239424271653961 6 2 70433890792962378 7 1 100712991028475110 8 6 16374735225525847 9 3 38964226065018266 10 3 63551609936599567 11 7 131094013854973507 12 8 13524853495456270 13 9 61205215744372194 14 13 9866222...
output:
78951874337377302 32581588916288103 136620750771756447 78156965674021138 41409957201679851 83908970598946206 22333028407348381 21739555965320482 111938868869719497 109840001971146954 78367769847418061 111288476107882150 106088437815366719 31385084858156502 29020476730829680 62342183965154174 1200780...
result:
ok 100000 numbers
Test #11:
score: 0
Accepted
time: 57ms
memory: 3716kb
input:
2937 11131 100000 2 1 38591812152054303 3 1 98523450159916322 4 3 87594749582696232 5 3 137180283106258524 6 2 120140192600896192 7 4 47548803322236416 8 1 35455244040603361 9 1 34148819233356770 10 8 6546694308869984 11 8 73921780737063049 12 4 27371451415625699 13 8 9665034188703734 14 5 674878987...
output:
70732012005799345 24113681136859923 92818054703699007 116503414641764372 99891709114828804 942803664217900 5371003395162933 126719333553172159 14073685604517313 90281276323307536 12882006203203890 5589980249805607 75382364867209589 25842978178984602 84262193200348589 22020698748435480 24614665582819...
result:
ok 100000 numbers
Test #12:
score: 0
Accepted
time: 66ms
memory: 3616kb
input:
1379 54037 100000 2 1 70687391757929033 3 2 118981364988924464 4 1 99934939938612997 5 4 119888276422806471 6 2 16547264691190392 7 6 69976501172978361 8 4 102614495250574796 9 6 125352664675673102 10 9 89066082629883215 11 4 1793321822406083 12 5 22005543166284780 13 5 124985067485601512 14 10 4854...
output:
49462696614839239 60791107305588205 22780613862023989 128946111963818791 109967384094879549 55315740126382967 102427614612098833 43311624861775496 116763178406809481 948709738155655 130587999154431330 70506358354045866 128691503125189662 33591214338794623 83087934482132668 22702341597756000 14159122...
result:
ok 100000 numbers
Test #13:
score: 0
Accepted
time: 48ms
memory: 3556kb
input:
100 99 100000 6 52 206007632450225211 52 29 313901991925203973 29 34 391372119941123743 34 93 140839370840938729 93 63 591433235933498211 63 45 811136933533572427 45 17 414003886618728318 17 11 309815180074851058 11 69 912536029006734893 69 38 778750422252237971 38 2 919571508448517880 2 36 76740602...
output:
1129948272554048600 875461056356943957 114967002443975506 969890353561961007 246788845417483376 677857433285040777 692766518759480382 522721224465230457 542262990839757567 1082000337901839822 626282160886545408 308851150390105567 859681443149601001 1045926842981643411 316290387637379873 104148261059...
result:
ok 100000 numbers
Test #14:
score: 0
Accepted
time: 57ms
memory: 3804kb
input:
8316 8315 100000 7385 7502 255449334338260274 7502 7461 256052186765987513 7461 824 918310200719062494 824 2712 257312954758128156 2712 5469 404900808074943541 5469 1278 462848683635227367 1278 5495 70390788085001721 5495 2144 145368174747249046 2144 4479 11304684541528526 4479 6852 7513962605814797...
output:
55851103389854671 518822560101020833 1108999214656416904 907245932138353096 721243960709779081 661395369684057304 715351722039897483 323588234784920707 155279215782404188 84068505061277733 786960773260763049 434499658626408437 508945268707963027 59764948792165596 439011650441283390 53648208421929001...
result:
ok 100000 numbers
Test #15:
score: 0
Accepted
time: 55ms
memory: 3720kb
input:
10000 9999 100000 3320 1263 288954032015928891 1263 2115 444836121941850831 2115 1174 236815585738801894 1174 1702 982773469069043489 1702 2288 698049167741605920 2288 8381 212041535316813597 8381 5048 775913161686795966 5048 1219 247085324932515813 1219 756 308801543462631507 756 9786 2746051643629...
output:
1044566880808630377 1058204316118272328 765599538572509436 1124289572121247306 1001111602752908713 633221928939169135 1151540539245498687 466913788005410393 1130096206269911169 524493057776305904 690663765357693005 228052285975147837 428176252336522816 1045960506339260956 85326518455219641 365909325...
result:
ok 100000 numbers
Test #16:
score: 0
Accepted
time: 12ms
memory: 3632kb
input:
400 10000 10000 153 384 114439150736771944 153 228 334043168064706977 228 356 27305346377465182 153 194 250970461839740124 228 372 55531278771863187 384 148 449605722702002561 384 352 322293477547814729 384 48 376736239216421315 148 115 471279260258511733 115 57 141378260567067626 372 306 9717869377...
output:
117273012570423296 400391411272253440 134882189505462272 436758763383291904 500573709589807104 512902675205980160 399443232817152000 540867512212914176 32206877420945408 467807988204175360 528772961616789504 146622401004699648 320059326515380224 331834902775332864 461787882869227520 2638468976245473...
result:
ok 10000 numbers
Test #17:
score: 0
Accepted
time: 12ms
memory: 3612kb
input:
5000 10000 10000 4000 972 206754506211981 4000 3132 387070055851466 4000 887 912222399954959 972 3599 982865593910521 3599 4416 605845194460298 4000 44 328112878157863 3132 1175 894674160054655 1175 1404 378414344708652 44 713 136906548471650 1175 4773 947093879944384 713 1476 910878018328403 4000 4...
output:
316377873822777344 181269885001662464 70931694131085312 168884986026393600 255579278853275648 229683580995895296 110338190870577152 486388759756013568 61924494876344320 3377699720527872 443604563295993856 564075853328154624 290482175965396992 399694466929131520 9007199254740992 249949779319062528 26...
result:
ok 10000 numbers
Test #18:
score: 0
Accepted
time: 79ms
memory: 3724kb
input:
10000 100000 100000 4419 3861 42795 3861 8236 46271 8236 2156 21014 4419 6937 6807 8236 8310 60155 8236 4719 58480 8310 2521 47060 4419 4159 1428 6937 2813 52329 4419 7698 408799372457174875 6937 5342 408799372457191911 8310 761 408799372457165485 7698 7164 20711 6937 8994 408799372457191001 4419 21...
output:
452933662398742528 389792109082574848 169722464946618368 57157802830200832 362515229867573248 436383262998855680 268467669297594368 419747353813647360 232600337801674752 288680708423680000 128092143062810624 477141603754442752 386539558330368000 572114573048741888 291834312971255808 2892236578745876...
result:
ok 100000 numbers
Test #19:
score: 0
Accepted
time: 3ms
memory: 3560kb
input:
61 60 3721 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 671088...
output:
0 1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 65535 131071 262143 524287 1048575 2097151 4194303 8388607 16777215 33554431 67108863 134217727 268435455 536870911 1073741823 2147483647 4294967295 8589934591 17179869183 34359738367 68719476735 137438953471 274877906943 549755813887 1099...
result:
ok 3721 numbers
Test #20:
score: 0
Accepted
time: 2ms
memory: 3656kb
input:
42 61 1 1 2 1048576 1 3 112975661028499096 3 4 1572864 4 1 112975661028499096 1 5 500585112346315942 5 6 786432 6 1 500585112346315942 1 7 857125438957885079 7 8 393216 8 1 857125438957885079 1 9 893089428615776288 9 10 196608 10 1 893089428615776288 1 11 119583402315685043 11 12 98304 12 1 11958340...
output:
1
result:
ok 1 number(s): "1"
Test #21:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
82 121 1 1 2 1099511627776 1 3 639989175320256304 3 4 1649267441664 4 1 639989175320256304 1 5 276460697324009764 5 6 824633720832 6 1 276460697324009764 1 7 182431325180738185 7 8 412316860416 8 1 182431325180738185 1 9 552127006504542916 9 10 206158430208 10 1 552127006504542916 1 11 2544483459423...
output:
1
result:
ok 1 number(s): "1"
Test #22:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
118 175 1 1 2 288230376151711744 1 3 694638340815405580 3 4 432345564227567616 4 1 694638340815405580 1 5 820139053026026968 5 6 216172782113783808 6 1 820139053026026968 1 7 499046115118231170 7 8 108086391056891904 8 1 499046115118231170 1 9 276697635505463386 9 10 54043195528445952 10 1 276697635...
output:
1
result:
ok 1 number(s): "1"
Test #23:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
2 1 4 1 2 1000000000000000000 1 2 2 2 2 1 1 1
output:
1000000000000000000 0 1000000000000000000 0
result:
ok 4 number(s): "1000000000000000000 0 1000000000000000000 0"