QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#650367#1339. Consistent TradingAfterlife#WA 27ms9396kbC++20981b2024-10-18 14:50:522024-10-18 14:50:56

Judging History

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

  • [2024-10-18 14:50:56]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:9396kb
  • [2024-10-18 14:50:52]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=200020;
int mod,n,m;
vector<pair<int,int> > G[N];
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1LL*ans*a%mod;
        a=1LL*a*a%mod;
        b>>=1;
    }
    return ans;
}
bool vis[N];
int g[N];
void dfs(int u,int x){
    vis[u]=1;
    g[u]=x;
    for(auto [v,_w]:G[u]){
        int w=_w<0?qpow(-_w,mod-2):_w;
        if(vis[v]){
            if(1LL*x*qpow(g[v],mod-2)%mod*w%mod!=1){
                cout<<"No\n";
                exit(0);
            }
        }
        else{
            dfs(v,1LL*x*w%mod);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    mod=1e9+7;
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v,x;
        cin>>u>>v>>x;
        G[u].emplace_back(v,x);
        G[v].emplace_back(u,-x);
    }
    dfs(1,1);
    mod=1e9+9;
    memset(vis,0,sizeof(vis));
    dfs(1,1);
    cout<<"Yes\n";
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3636kb

input:

4 4
1 2 2
2 3 2
3 4 2
4 2 3

output:

No

result:

ok "No"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

4 3
1 2 7
2 3 5
4 1 2

output:

Yes

result:

ok "Yes"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

4 4
1 2 101
2 3 99
1 4 100
4 3 100

output:

No

result:

ok "No"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3836kb

input:

5 6
3 1 4
2 3 4
5 4 15
2 1 16
2 4 20
5 3 3

output:

Yes

result:

ok "Yes"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

10 17
6 5 265734983
4 9 631933499
1 2 450290420
7 1 577953100
3 8 92694360
10 3 761646389
3 6 392253210
10 1 449374360
6 4 851489585
6 7 63621701
3 1 576785719
3 2 634083860
10 9 429292904
5 2 199416975
10 5 839205223
7 9 596491153
3 5 652832022

output:

No

result:

ok "No"

Test #6:

score: 0
Accepted
time: 1ms
memory: 3772kb

input:

4 2
1 3 64273202
2 4 384367629

output:

Yes

result:

ok "Yes"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3828kb

input:

5 2
5 3 497476572
5 4 364850118

output:

Yes

result:

ok "Yes"

Test #8:

score: 0
Accepted
time: 1ms
memory: 3880kb

input:

7 1
5 4 258406601

output:

Yes

result:

ok "Yes"

Test #9:

score: 0
Accepted
time: 1ms
memory: 3884kb

input:

4 3
4 3 504856579
1 4 646945713
2 3 388357231

output:

Yes

result:

ok "Yes"

Test #10:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

7 21
2 6 663227492
7 4 461354276
3 4 28152109
6 4 358823726
5 2 619487277
3 7 260147635
3 1 877405198
5 1 955891101
1 4 957499076
3 2 384665589
7 6 368531672
7 1 914427926
1 2 97380293
2 7 787748249
6 3 293843142
4 5 962318607
7 5 44905554
5 6 510079867
1 6 325095627
3 5 347330348
2 4 453400205

output:

No

result:

ok "No"

Test #11:

score: 0
Accepted
time: 1ms
memory: 3636kb

input:

8 13
7 8 522627804
7 2 400792198
6 7 220572477
8 6 772420713
4 5 949106732
1 2 867088911
6 3 850851737
1 4 541599109
4 6 310148807
2 6 481974581
1 6 792195677
4 2 311938108
7 1 460640026

output:

No

result:

ok "No"

Test #12:

score: 0
Accepted
time: 1ms
memory: 3636kb

input:

7 17
5 6 278219751
1 2 888194392
7 5 422277480
4 1 438560464
4 6 86173934
6 7 738154829
2 5 149378290
7 2 781306443
5 3 290126418
7 1 910494332
1 5 432352620
2 3 69931343
1 6 257768620
4 2 296685964
3 4 111244605
6 3 65247518
4 5 854386607

output:

No

result:

ok "No"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3768kb

input:

2 1
1 2 11120644

output:

Yes

result:

ok "Yes"

Test #14:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

9 30
1 9 767960951
4 1 843961520
4 5 753611695
7 8 994435066
2 5 996986937
6 7 979505444
7 1 797888527
8 5 132536139
3 2 190075945
4 8 781527916
9 8 678009694
5 6 366110865
4 3 902969662
2 1 924897880
3 9 249564963
2 6 22491710
6 4 555261264
3 8 918118198
6 3 861966090
5 3 422916723
2 8 212080020
1 ...

output:

No

result:

ok "No"

Test #15:

score: 0
Accepted
time: 6ms
memory: 6244kb

input:

69862 16243
61420 64532 280460887
32912 33645 212682531
22783 31406 94042606
47240 23816 532005326
56757 36042 794651906
38378 65261 5084078
15179 17842 554767388
24796 14480 692889976
22928 18909 780109469
13637 12354 412459465
34232 2209 724813520
9922 60865 713394801
14332 38843 669586503
53206 6...

output:

Yes

result:

ok "Yes"

Test #16:

score: 0
Accepted
time: 4ms
memory: 4176kb

input:

827 21822
18 821 642462789
513 112 311836307
240 658 73121766
16 246 579367910
208 423 117505817
179 530 851348979
488 485 678468520
779 486 453668275
801 647 771631421
113 50 354211008
250 522 133629880
497 421 707140103
228 643 267692035
640 208 703367050
324 429 541669576
801 172 545505111
530 34...

output:

No

result:

ok "No"

Test #17:

score: 0
Accepted
time: 4ms
memory: 4736kb

input:

21170 14190
12190 1919 829256837
13172 14442 754634128
13158 17979 219895002
7962 3318 745811773
2000 12434 619598111
4130 12688 716508065
286 15300 667007847
20755 19573 326606412
17386 16179 432664111
17037 20764 282071877
4295 4361 897036638
6700 7818 59183942
17772 2272 862602730
14386 1303 3994...

output:

No

result:

ok "No"

Test #18:

score: 0
Accepted
time: 17ms
memory: 6368kb

input:

9663 84196
8297 1879 292786372
9215 397 652140130
7444 9475 230784857
3715 5438 451941544
940 2271 372156459
2571 7053 731142133
450 5554 150223192
9330 4598 320338112
3889 5406 767450300
7115 2515 753332496
1397 4858 787930543
4022 5066 1956218
5284 4664 835728412
9339 1409 756955717
2837 7517 3945...

output:

No

result:

ok "No"

Test #19:

score: 0
Accepted
time: 12ms
memory: 5756kb

input:

24363 46728
11279 14632 838193751
22537 8614 985775026
2002 239 575454959
14348 19836 897828533
16269 16405 30369733
18692 20536 172894860
21749 8322 804563413
6958 886 582454166
12061 17305 480341825
23654 3377 593320639
19955 801 861707475
11628 4705 905166352
16306 23449 342264020
14163 6023 7103...

output:

No

result:

ok "No"

Test #20:

score: 0
Accepted
time: 27ms
memory: 9132kb

input:

75774 97925
27616 29383 814253970
46864 71571 495830926
6229 28188 834105682
53892 48713 492017500
61104 61677 266373726
47725 70995 789552512
72121 15109 715629932
73020 68371 835662806
9441 6566 664939615
5044 45133 295097395
12319 47956 692063837
45460 56387 949953406
67952 9234 415898495
74535 2...

output:

No

result:

ok "No"

Test #21:

score: 0
Accepted
time: 7ms
memory: 5344kb

input:

3257 54391
1478 1881 405181854
2268 2418 266963650
1942 3061 811310494
1309 2846 602605161
1285 1372 880180026
1883 607 269944530
2204 2370 125240324
3105 911 933126555
317 2218 89577732
2058 582 92554043
2052 1675 533667739
1150 275 786833047
2918 2843 621676173
886 2576 647436671
1732 1920 4449942...

output:

No

result:

ok "No"

Test #22:

score: -100
Wrong Answer
time: 25ms
memory: 9396kb

input:

93836 96085
26437 6661 172197286
72936 28639 8334549
67103 81135 845010863
46695 90447 845089693
15590 82835 672972514
28797 37047 588092133
52927 19300 71955055
37181 22230 351020581
53822 49645 790537805
72151 88523 917547217
89100 14757 357043887
88802 63473 520258996
34870 60259 114665520
29198 ...

output:

Yes

result:

wrong answer 1st words differ - expected: 'No', found: 'Yes'