QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#650371 | #1339. Consistent Trading | Afterlife# | WA | 27ms | 9436kb | C++20 | 1.0kb | 2024-10-18 14:52:36 | 2024-10-18 14:52:36 |
Judging History
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);
mod=1026516721;
memset(vis,0,sizeof(vis));
dfs(1,1);
cout<<"Yes\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3628kb
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: 0ms
memory: 3820kb
input:
4 3 1 2 7 2 3 5 4 1 2
output:
Yes
result:
ok "Yes"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3700kb
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: 3812kb
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: 3616kb
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: 3892kb
input:
4 2 1 3 64273202 2 4 384367629
output:
Yes
result:
ok "Yes"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3860kb
input:
5 2 5 3 497476572 5 4 364850118
output:
Yes
result:
ok "Yes"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3892kb
input:
7 1 5 4 258406601
output:
Yes
result:
ok "Yes"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
4 3 4 3 504856579 1 4 646945713 2 3 388357231
output:
Yes
result:
ok "Yes"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3684kb
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: 3624kb
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: 3700kb
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: 3816kb
input:
2 1 1 2 11120644
output:
Yes
result:
ok "Yes"
Test #14:
score: 0
Accepted
time: 1ms
memory: 5716kb
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: 3ms
memory: 6344kb
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: 4252kb
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: 0ms
memory: 4836kb
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: 14ms
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: 5812kb
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: 9128kb
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: 11ms
memory: 5316kb
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: 23ms
memory: 9436kb
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'