QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#56665#877. Company At Dangert3alaMsMs#AC ✓57ms7172kbC++232.2kb2022-10-21 00:03:302022-10-21 00:03:34

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-21 00:03:34]
  • 评测
  • 测评结果:AC
  • 用时:57ms
  • 内存:7172kb
  • [2022-10-21 00:03:30]
  • 提交

answer

/// :3
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;

#include "bits/stdc++.h"

#define pb push_back
#define F first
#define S second
#define f(i, a, b)  for(int i = a; i < b; i++)
#define all(a)  a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(x) (int)(x).size()
#define mp(x,y) make_pair(x,y)
#define popCnt(x) (__builtin_popcountll(x))
#define int ll

using ll = long long;
using ii = pair<int, int>;
using ull = unsigned long long;

const int N = 3e5+5, LG = 18, MOD = (119 << 23) + 1;
const long double PI = acos(-1);
const long double EPS = 1e-7;
const int dx[] = {1,1,0,-1,-1,-1,0,1};
const int dy[] = {0,1,1,1,0,-1,-1,-1};
int p[10005];
int get(int i){return i == p[i]? i : p[i]=get(p[i]);}
int n, m, q;
vector<ii> adj[10004];
int xr[N];
void dfs(int node, int par) {

    for(auto e : adj[node]) if(e.F != par){
        xr[e.F] = xr[node] ^ e.S;
        dfs(e.F, node);
    }

}
struct G {
	vector<ll> setOfXors;
	void ins(ll x) {	///Add X to Gaussian Basis
		for (auto v : setOfXors)
			x = min(x, x ^ v);
		if (x)
			setOfXors.push_back(x);
	}
	ll qry(ll x) { ///Get maximum subsequence XOR ^ x
		for (auto v : setOfXors)
			x = max(x, x ^ v);
		return x;
	}
} gauss;
void doWork() {
    cin >> n >> m >> q;
    iota(p,p+n+1,0);
    vector<array<int, 3> > edges;
    while(m--) {
        int u, v, w;
        cin >> u >> v >> w;
        if(get(u) != get(v)) {
            adj[u].pb({v, w});
            adj[v].pb({u, w});
            p[get(u)] = get(v);
        }   else {
            edges.push_back({u, v, w});
        }
    }

    dfs(1, 1);

    for(auto e : edges) {
        int u = e[0], v = e[1], w = e[2];
        gauss.ins(xr[u]^xr[v]^w);
    }

    while(q--) {
        int u, v;
        cin >> u >> v;
        int val = xr[u] ^ xr[v];
        for(auto v : gauss.setOfXors)
            val = min(val, val ^ v);
        cout << val << '\n';
    }

}
int32_t main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE
    int t = 1;
//    cin >> t;
    while (t--) {
        doWork();
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 3796kb

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: 3880kb

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: 5756kb

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: 3860kb

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: 56ms
memory: 6644kb

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: 51ms
memory: 6676kb

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: 57ms
memory: 6676kb

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: 57ms
memory: 7172kb

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: 4200kb

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: 27ms
memory: 4768kb

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: 24ms
memory: 4308kb

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: 45ms
memory: 5300kb

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: 18ms
memory: 3812kb

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: 25ms
memory: 4600kb

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: 29ms
memory: 4660kb

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: 5ms
memory: 4140kb

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: 11ms
memory: 4348kb

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: 56ms
memory: 7168kb

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: 3796kb

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: 3888kb

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: 3800kb

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: 1ms
memory: 3800kb

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: 3876kb

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"