QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#585348#1339. Consistent Trading112412451WA 29ms12036kbC++142.9kb2024-09-23 20:28:112024-09-23 20:28:11

Judging History

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

  • [2024-09-23 20:28:11]
  • 评测
  • 测评结果:WA
  • 用时:29ms
  • 内存:12036kb
  • [2024-09-23 20:28:11]
  • 提交

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";
}

Details

Tip: Click on the bar to expand more detailed information

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'