QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#35163 | #877. Company At Danger | AutumnKite | WA | 102ms | 3660kb | C++17 | 1.4kb | 2022-06-14 10:09:23 | 2022-06-14 10:09:24 |
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[fx];
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";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3648kb
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: 0ms
memory: 3552kb
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: 29ms
memory: 3644kb
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: 3620kb
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: 102ms
memory: 3556kb
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: 96ms
memory: 3508kb
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: 96ms
memory: 3548kb
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: 74ms
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: 3564kb
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: -100
Wrong Answer
time: 64ms
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:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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:
wrong answer 1st numbers differ - expected: '78951874337377302', found: '0'