QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#864707	#6679. Not Another Path Query Problem	Zhoumurui	WA	1439ms	52224kb	C++14	1.0kb	2025-01-20 21:59:34	2025-01-20 21:59:40

Judging History

This is the latest submission verdict.

[2025-01-20 21:59:40]
Judged

Verdict: WA
Time: 1439ms
Memory: 52224kb

Show

[2025-01-20 21:59:34]
Submitted

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct uset{
    int f[100005];
    int find(int u){
        if (!f[u])return u;
        return f[u]=find(f[u]);
    }
    void add(int u,int v){
        u=find(u);
        v=find(v);
        if (u!=v)f[v]=u;
    }
}U[64];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,q,v;
    cin>>n>>m>>q>>v;
    
    for (int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        if ((w&v)>=v)U[61].add(u,v);
        for (int i=60;i>=0;i--){
            if ((w&(1<<i))>(v&(1<<i))){
                U[i].add(u,v);
            }
            else if ((w&(1<<i))<(v&(1<<i)))break;
        }
    }
    while (q--){
        int u,v;
        cin>>u>>v;
        int flag=0;
        for (int i=61;i>=0;i--){
            if (U[i].find(u)==U[i].find(v)){
                flag=1;
                break;
            }
        }
        if (flag)cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3584kb

input:

output:

Yes
No
Yes
No

result:

ok 4 token(s): yes count is 2, no count is 2

Test #2:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

output:

Yes

result:

ok YES

Test #3:

score: 0

Accepted

time: 6ms

memory: 4096kb

input:

100 2000 50000 0
32 52 69658009083393280
26 38 868250171554967916
87 32 743903879320440454
22 15 19782587273744714
57 98 845866434191429143
42 95 1145336983294966993
67 40 1036117659380117375
46 24 265457274847122243
63 44 438254608190938148
28 23 992625102587165494
57 87 558124114385470345
6 17 535...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 50000 token(s): yes count is 50000, no count is 0

Test #4:

score: 0

Accepted

time: 5ms

memory: 4096kb

input:

100 2000 50000 0
6 10 1152921503398360575
70 50 1147995692480249852
85 50 1152921500294021032
74 27 1078952220075835391
12 7 1152840139402113023
94 18 246566425809715199
15 3 1152859588138927091
13 17 1152921504302759415
95 30 70321567232249231
76 40 576455254460071931
83 33 825457230579891955
36 71...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 50000 token(s): yes count is 50000, no count is 0

Test #5:

score: 0

Accepted

time: 5ms

memory: 4096kb

input:

100 2000 50000 0
32 30 1152921504602652671
8 85 1152914907537080319
19 74 1152921504605667327
62 100 1151795604687421439
87 32 1079738010662076415
57 76 1152921504606842879
70 8 1152921504606846975
95 41 1152921504069976059
88 41 1152903912420769791
74 50 1152499292141256703
71 47 576460752295034879...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 50000 token(s): yes count is 50000, no count is 0

Test #6:

score: 0

Accepted

time: 4ms

memory: 3968kb

input:

100 2000 50000 0
6 83 1152921504606846975
41 67 1152771969951725565
66 18 1152917101527171071
42 100 1152921504606846975
42 36 1152885220186128383
68 6 1062849510985693150
63 37 11607128887709333
77 94 195895037245918453
12 66 1152921504606846975
43 68 801313368834621047
16 15 864549566333059007
67 ...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 50000 token(s): yes count is 50000, no count is 0

Test #7:

score: 0

Accepted

time: 364ms

memory: 50176kb

input:

100000 500000 500000 0
57409 92310 855506197841388351
48893 50956 635095737920170434
60473 38646 356425024348070344
24975 49205 1002259844174974454
64205 19718 1007224495019887036
89453 80562 805646901543302037
37980 78408 130784586947510355
87951 78976 521293221248312596
76010 60701 100242203282273...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 500000 token(s): yes count is 499951, no count is 49

Test #8:

score: 0

Accepted

time: 602ms

memory: 51968kb

input:

100000 500000 500000 0
11668 2167 799309698684681841
38924 90176 494164432953671679
6591 69603 1098876105491741695
46900 71892 1131520541564338171
53922 65764 1008166035624296191
79522 97248 495689599221308844
42217 85199 1116329620194459591
42341 50139 501547825112275970
38967 33048 609203269593661...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 500000 token(s): yes count is 499943, no count is 57

Test #9:

score: 0

Accepted

time: 1439ms

memory: 52224kb

input:

100000 500000 500000 0
23810 63495 1152917106543558647
9000 99475 1134907106097364991
15 28164 1152920954716815359
58059 4881 1134907106097364991
3191 91374 1134344156143943679
85921 23690 1152920954851033087
84285 6286 1080858954176659455
63682 44759 1134907105292058623
39860 8182 11529215046068459...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 500000 token(s): yes count is 499944, no count is 56

Test #10:

score: 0

Accepted

time: 1201ms

memory: 52096kb

input:

100000 500000 500000 0
10772 40649 179621667490781446
88648 45519 576460752269344703
51682 33956 1150669704624860927
54653 12331 864690836397358838
20705 72074 1080863910568919039
54092 83726 1152909891011084031
52592 88011 1152921504606846975
35474 6914 1152921504606846975
36990 92070 1116326841007...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 500000 token(s): yes count is 499961, no count is 39

Test #11:

score: -100

Wrong Answer

time: 0ms

memory: 3968kb

input:

50 1000 2000 1039591541983998747
50 19 807838188774349732
38 29 649665922060871144
27 13 135914717407793707
44 12 936258227191225042
16 9 348410184150972152
8 37 1040614863781876726
3 6 1003718816381445902
34 38 1059631448265320959
28 3 274488581842134658
29 17 538067399161425294
34 4 50910691842533...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

wrong answer expected NO, found YES [1st token]