QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#585348 | #1339. Consistent Trading | 112412451 | WA | 29ms | 12036kb | C++14 | 2.9kb | 2024-09-23 20:28:11 | 2024-09-23 20:28:11 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <assert.h>
#include <unordered_set>
#include <unordered_map>
#pragma warning(disable:4996)
#define fi first
#define se second
using namespace std;
/*
rope c++
#include <ext/rope>
using namespace __gnu_cxx;
*/
/*
pbds c++ set전용
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
multiset을 쓰고 싶으면 위의 코드에서 마지막 줄만 아래 코드로 변경.(대신 erase가 정상작동 되지 않는다.)
#define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
이외에 범위를 늘리고 싶으면 타입변경하면 된다.
ex. int->ll, less_equal<ll>
*/
const long long INF = 2147483647;
const long long lINF = 9000000000000000000;
const long long nlINF = lINF / 100;
const int nINF = 1007483647;
unsigned long long MOD = 1000000007;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<short, short>sh_sh;
typedef pair<int, int> intint;
typedef pair<int, double> int_d;
typedef pair<double, double> dd;
typedef pair<intint, double> int2_d;
typedef pair<int, ll> intlong;
typedef pair<ll, ll> ll_ll;
typedef pair<intint, int> int2_int;
typedef pair<int, intint> int_int2;
typedef pair<ll, ll_ll> ll_ll2;
typedef pair<ll_ll, ll>ll2_ll;
typedef pair<intint, intint> int2_int2;
typedef pair<ll_ll, ll_ll> ll2_ll2;
typedef pair<char, int> char_int;
//{이동 위치,{+면 *수, -면 /수}}
vector<ll_ll>line[100001];
bool visit[100001];
ll cost[100001];
ll custom_pow(ll a, ll n) {
if (n == 0)return 1;
if (n == 1)return a;
ll sum = custom_pow(a, n / 2);
sum = (sum * sum) % MOD;
if (n % 2 == 1)sum = (sum * a) % MOD;
return sum;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, m, a, b, c;
cin >> n >> m;
while (m--) {
cin >> a >> b >> c;
line[a].push_back({ b,c });
line[b].push_back({ a,-c });
}
for (int i = 1; i <= n; i++) {
if (visit[i])continue;
visit[i] = true;
cost[i] = 1;
queue<ll_ll>arr;
arr.push({ i,1ll });
while (arr.size()) {
ll now_p = arr.front().fi;
ll now_cost = arr.front().se;
arr.pop();
for (ll_ll h : line[now_p]) {
ll new_p = h.fi;
ll new_cost = (now_cost * h.se) % MOD;
if (h.se < 0) {
new_cost = (now_cost * custom_pow(-h.se, MOD - 2)) % MOD;
}
if (!visit[new_p]) {
visit[new_p] = true;
cost[new_p] = new_cost;
arr.push({ new_p,new_cost });
continue;
}
if (cost[new_p] == new_cost)continue;
cout << "No";
return 0;
}
}
}
cout << "Yes";
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 6760kb
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: 5964kb
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: 6408kb
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: 5952kb
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: 5836kb
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: 6156kb
input:
4 2 1 3 64273202 2 4 384367629
output:
Yes
result:
ok "Yes"
Test #7:
score: 0
Accepted
time: 0ms
memory: 6756kb
input:
5 2 5 3 497476572 5 4 364850118
output:
Yes
result:
ok "Yes"
Test #8:
score: 0
Accepted
time: 1ms
memory: 6124kb
input:
7 1 5 4 258406601
output:
Yes
result:
ok "Yes"
Test #9:
score: 0
Accepted
time: 0ms
memory: 5904kb
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: 6156kb
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: 5964kb
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: 6120kb
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: 6224kb
input:
2 1 1 2 11120644
output:
Yes
result:
ok "Yes"
Test #14:
score: 0
Accepted
time: 0ms
memory: 6520kb
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: 10ms
memory: 7520kb
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: 5ms
memory: 7684kb
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: 5ms
memory: 6824kb
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: 20ms
memory: 11588kb
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: 14ms
memory: 8784kb
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: 29ms
memory: 11668kb
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: 8ms
memory: 8972kb
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: 0
Accepted
time: 25ms
memory: 12036kb
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:
No
result:
ok "No"
Test #23:
score: 0
Accepted
time: 8ms
memory: 7540kb
input:
59423 8731 48994 48904 532953843 29413 16950 230007051 45437 49477 783665121 58732 15777 598315126 51498 1669 127041842 3281 50778 658262445 4446 33237 175452201 5693 14091 6930658 17351 6734 835152427 54859 57408 528373972 7167 27120 979438685 29434 21874 796366418 26137 11725 186239191 19239 36979...
output:
Yes
result:
ok "Yes"
Test #24:
score: 0
Accepted
time: 10ms
memory: 8064kb
input:
1669 44970 1289 881 580615741 199 305 544628212 124 987 889744111 651 5 650335708 1016 723 372958146 183 1315 485567780 1322 1305 782416327 262 1409 793841827 980 489 680565826 37 615 662957321 1378 1643 481203237 1029 1167 816371526 995 372 399184355 39 1462 310714994 98 1303 623837314 537 59 79809...
output:
No
result:
ok "No"
Test #25:
score: 0
Accepted
time: 1ms
memory: 5896kb
input:
4 4 1 2 999999996 2 3 999999999 1 4 999999997 4 3 999999998
output:
No
result:
ok "No"
Test #26:
score: 0
Accepted
time: 1ms
memory: 5960kb
input:
4 4 1 2 999999999 2 3 999999999 1 4 999999999 4 3 1000000000
output:
No
result:
ok "No"
Test #27:
score: 0
Accepted
time: 1ms
memory: 6248kb
input:
4 4 1 2 1000000000 2 3 1000000000 1 4 999999999 4 3 1000000000
output:
No
result:
ok "No"
Test #28:
score: 0
Accepted
time: 1ms
memory: 6124kb
input:
3 3 1 2 1 2 3 1 3 1 1
output:
Yes
result:
ok "Yes"
Test #29:
score: -100
Wrong Answer
time: 4ms
memory: 7056kb
input:
92816 621 58624 86675 142979215 9703 77323 626699040 91253 88207 593363841 65249 72303 7134145 31555 91846 644098701 89255 73558 112862491 36790 86148 14774701 57934 75241 222857121 54408 79027 37572766 78990 84528 442171327 80276 64041 9229135 88464 80293 305432254 70572 84179 11271261 84310 34111 ...
output:
Yes
result:
wrong answer 1st words differ - expected: 'No', found: 'Yes'