QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#35163#877. Company At DangerAutumnKiteWA 102ms3660kbC++171.4kb2022-06-14 10:09:232022-06-14 10:09:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-14 10:09:24]
  • 评测
  • 测评结果:WA
  • 用时:102ms
  • 内存:3660kb
  • [2022-06-14 10:09:23]
  • 提交

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'