QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721099#5548. Increase the Toll Feeswjt#AC ✓99ms33772kbC++142.6kb2024-11-07 15:14:332024-11-07 15:14:37

Judging History

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

  • [2024-11-07 15:14:37]
  • 评测
  • 测评结果:AC
  • 用时:99ms
  • 内存:33772kb
  • [2024-11-07 15:14:33]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 100005
#define M 200005
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
int n, m, fa[N], cnt;
struct edge {
	int u, v, w;
	bool tag;
	bool operator < (const edge& t) const { return w < t.w; };
}e[M];

int find(int u) {
	return fa[u] == u ? u : fa[u] = find(fa[u]);
}
vector <edge> pre;
void clear() {
	for (int i = 1; i <= n; i++)
		fa[i] = i;
	cnt = 0;
}

struct node {
	int v, w;
};
vector <node> son[N];
int f[N][20], Max[N][20];


int dep[N], val[N];

void dfs(int u, int fa) {
	dep[u] = dep[fa] + 1;
	f[u][0] = fa;
	for (int i = 1; (1 << i) <= dep[u]; i++) {
		f[u][i] = f[f[u][i - 1]][i - 1];
	}
	for (int i = 0; i < son[u].size(); i++) {
		int v = son[u][i].v, w = son[u][i].w;
		if (v == fa) continue;
		val[v] = w;
		dfs(v, u);
	}
}

void fun(int u, int fa) {
	Max[u][0] = val[u];
	for (int i = 1; i <= 19; i++) {
		Max[u][i] = max(Max[ f[u][i - 1] ][i - 1], Max[u][i - 1]);
	}
	for (int i = 0; i < son[u].size(); i++) {
		int v = son[u][i].v;
		if (v != fa) fun(v, u);
	}
}
int get(int s, int t) {
	int res = -INF;
	if (dep[s] < dep[t]) swap(s, t);
	for (int i = 19; i >= 0; i--) {
		if (dep[s] - (1 << i) >= dep[t]) {
			res = max(res, Max[s][i]);
			s = f[s][i];
		}
	}
	if (s == t) return res;
	for (int i = 19; i >= 0; i--) {
		if (f[s][i] != f[t][i]) {
			res = max(res, max(Max[s][i], Max[t][i]) );
			s = f[s][i];
			t = f[t][i];
		}
	}
	return max(res, max(Max[s][0],Max[t][0]));
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;

	for (int i = 1; i <= m; i++) {
		cin >> e[i].u >> e[i].v >> e[i].w;
		e[i].tag = 1;
	}
	sort(e + 1, e + m + 1);
	clear();
	for (int i = 1; i <= m; i++) {
		int u = e[i].u, v = e[i].v;
		int fu = find(u), fv = find(v);
		if (fu == fv) continue;
		fa[fv] = fu;
		e[i].tag = 0;
		pre.push_back(e[i]);
		cnt++;
		if (cnt == n - 1) break;
	}

	clear();
	for (int i = 1; i <= m; i++) {
		if (!e[i].tag) continue;
		int u = e[i].u, v = e[i].v;
		int fu = find(u), fv = find(v);
		if (fu == fv) continue;
		fa[fv] = fu;

		son[u].push_back({ v,e[i].w });
		son[v].push_back({ u,e[i].w });

		cnt++;
		if (cnt == n - 1) break;
	}
	if (cnt < n - 1) {
		cout << -1;
		return 0;
	}

	int rt = 1;
	dfs(rt, 0);
	val[rt] = -INF;
	fun(rt, 0);

	ll ans = 0;
	for (int i = 0; i < pre.size(); i++) {
		int s = pre[i].u, t = pre[i].v;
		//cout << s << " " << t << " " << pre[i].w << " ";
		ll tmp = (ll)get(s, t);
		//cout << tmp << " " << endl;
		ans += tmp + 1LL - pre[i].w;
	}
	cout << ans;
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 11912kb

input:

4 6
1 2 2
1 3 5
1 4 5
2 3 3
2 4 5
3 4 4

output:

9

result:

ok single line: '9'

Test #2:

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

input:

3 4
1 2 3
2 3 4
1 3 5
1 3 10

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 2ms
memory: 11852kb

input:

5 10
1 2 14
1 3 14
1 4 9
1 5 15
2 3 8
2 3 10
2 4 13
3 4 8
4 5 10
4 5 15

output:

21

result:

ok single line: '21'

Test #4:

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

input:

2 1
1 2 1

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 22ms
memory: 19424kb

input:

29171 100000
7223 21138 270743473
5598 27967 847631606
12666 26050 847631606
75 15747 270743473
8522 12955 847631606
6069 23750 270743473
18708 22605 847631606
16814 22169 847631606
11550 27119 847631606
562 15959 847631606
9400 11110 270743473
15325 23805 270743473
19169 24404 270743473
6649 12062 ...

output:

16827826868780

result:

ok single line: '16827826868780'

Test #6:

score: 0
Accepted
time: 54ms
memory: 12008kb

input:

47977 200000
10970 47321 440845807
1166 29708 767952745
319 37520 546280762
17581 29425 558321466
22079 26884 344816304
7479 44260 791002634
14685 44163 837529020
1537 10359 330017953
8634 27064 969738917
32950 37192 728271930
34751 42782 63025978
32540 34226 86057211
36786 46050 826927874
30444 436...

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 23ms
memory: 19352kb

input:

28825 57648
9446 22014 286256842
14902 20222 14175
3246 20218 80493268
1783 13768 931622563
11107 24862 918832025
25070 27312 98899079
8535 20222 16037
9184 17491 294248461
8799 17834 456827944
1152 11687 960740527
17849 23045 9706
5774 21436 444202963
5417 23045 3092
20222 20370 11232
16585 20222 1...

output:

28822649262260

result:

ok single line: '28822649262260'

Test #8:

score: 0
Accepted
time: 55ms
memory: 17740kb

input:

22253 200000
46 10310 674985053
2403 19582 788128238
5203 7897 985236456
2709 9034 824557880
14337 20524 230824854
19901 22177 99959362
5067 8568 570267383
13707 21474 610729058
7494 7860 109319713
14473 16182 794578653
21 17055 852110939
19320 21640 844993191
2443 21673 170358534
5941 9705 16465049...

output:

3270266304988

result:

ok single line: '3270266304988'

Test #9:

score: 0
Accepted
time: 19ms
memory: 17848kb

input:

24396 100000
2931 7546 930776437
29 7070 602517959
9822 15137 930776437
8704 9393 930776437
9948 19773 930776437
14323 16751 930776437
6249 19840 930776437
11692 16925 930776437
8806 13126 930776437
13600 23061 930776437
738 21253 930776437
8142 16750 930776437
3498 23353 930776437
8769 23254 930776...

output:

8007865595205

result:

ok single line: '8007865595205'

Test #10:

score: 0
Accepted
time: 43ms
memory: 10752kb

input:

20147 200000
8151 8515 682552832
9950 17609 401979729
2320 16777 623704514
12160 18944 584466480
14548 18229 573286673
1849 2446 288691450
12937 19825 748755808
15533 16212 931321301
960 4132 465223013
2102 19779 143370818
8177 10702 194163825
6217 8093 190716214
7912 17254 788498808
15915 16392 396...

output:

-1

result:

ok single line: '-1'

Test #11:

score: 0
Accepted
time: 42ms
memory: 22156kb

input:

44967 89932
4611 22256 288245643
13129 41735 40940
26585 28192 22377
13129 18756 35813
244 24542 392777697
3170 13129 10602
5106 13129 3108
12697 43383 520646529
8665 38358 657175335
8174 22928 146486000
13129 42450 29798
20450 31848 601056112
26585 35000 37292
166 29044 536220871
1775 13686 9371272...

output:

44963069583727

result:

ok single line: '44963069583727'

Test #12:

score: 0
Accepted
time: 42ms
memory: 13320kb

input:

100000 150000
61412 88694 183559127
63436 73299 894859967
26602 46436 786301216
1338 12025 782274652
23565 55101 978497921
8423 12177 987621555
26437 59897 512205670
25428 90394 99802072
34439 96521 36264639
3514 47608 31833243
27862 59455 161754672
13730 65287 750535148
8174 74169 84643097
77653 80...

output:

-1

result:

ok single line: '-1'

Test #13:

score: 0
Accepted
time: 57ms
memory: 30580kb

input:

100000 199998
1740 95147 410564287
14057 30242 975301572
44406 68640 99197243
25206 33319 147706560
36836 82726 532371198
20169 20381 157910525
27802 94319 355487781
74596 90242 153032027
27347 85192 206476264
10053 84568 938334959
70186 94117 154520026
56539 64797 284929069
3156 51928 346065715
652...

output:

199998

result:

ok single line: '199998'

Test #14:

score: 0
Accepted
time: 59ms
memory: 30724kb

input:

100000 199998
21029 24465 1
20281 70033 1000000000
80966 83405 1
182 91462 1
11471 80105 1
44728 64299 1000000000
28235 37983 1000000000
29478 73083 1000000000
39551 66918 1
44691 83002 1
6717 74353 1
8546 39620 1000000000
25795 72680 1000000000
18738 53936 1000000000
54601 98620 1000000000
30462 76...

output:

99999000000000

result:

ok single line: '99999000000000'

Test #15:

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

input:

2 2
1 2 1
1 2 1000000000

output:

1000000000

result:

ok single line: '1000000000'

Test #16:

score: 0
Accepted
time: 68ms
memory: 30828kb

input:

100000 199998
6428 66622 140276399
45806 66068 24480468
27996 75977 238456054
22694 40930 246531711
7996 65658 817165171
8354 88303 818881672
5417 28577 743249294
45892 78967 941072773
67230 86764 793683381
25148 94217 889440410
24364 76989 72031957
32897 70536 252745043
42569 98426 598450133
53879 ...

output:

33452348231419

result:

ok single line: '33452348231419'

Test #17:

score: 0
Accepted
time: 40ms
memory: 9204kb

input:

492 200000
243 351 729773927
25 119 546768431
60 137 442503509
1 208 521544290
116 241 616544481
144 327 197607774
83 205 486182087
52 450 429246768
68 476 370698523
102 439 997049507
289 317 781589140
271 383 499974515
99 436 807262087
177 364 673711522
432 492 968138053
203 319 653023170
164 228 3...

output:

-1

result:

ok single line: '-1'

Test #18:

score: 0
Accepted
time: 50ms
memory: 14540kb

input:

100000 200000
84171 84739 505815970
17361 59167 948077627
25317 90899 272978612
33900 84218 346991489
29646 94826 981152764
11714 36825 926502871
73525 80993 659061656
10733 16853 626788053
21943 45826 430265524
11089 20657 155519370
54702 94924 284275764
37517 67203 953992098
4102 74402 82177808
17...

output:

-1

result:

ok single line: '-1'

Test #19:

score: 0
Accepted
time: 55ms
memory: 15464kb

input:

100000 200000
13082 57199 149496420
10054 56294 824028907
43901 59605 103513168
35993 63404 622713142
4806 31530 908477965
44059 67910 724384248
64805 72179 531531848
68723 79372 172534233
11791 58535 322108128
37229 42105 920481936
6960 93050 610830465
24330 73863 76965699
32477 70010 226027749
519...

output:

-1

result:

ok single line: '-1'

Test #20:

score: 0
Accepted
time: 58ms
memory: 13288kb

input:

100000 200000
52710 55025 966150175
40113 62589 258741162
10398 41929 719940312
62569 96363 647085340
12545 85765 246861841
9434 85579 88351251
6932 33791 35910750
43583 79985 141207527
41399 43414 495405143
46414 57400 382398546
33375 81532 723786073
30896 40080 745877110
38136 92624 689836040
6917...

output:

-1

result:

ok single line: '-1'

Test #21:

score: 0
Accepted
time: 44ms
memory: 25896kb

input:

60000 200000
3771 28395 761400909
15553 31165 761400909
21428 28268 761400909
41028 42823 731118597
25461 58226 761400909
20837 21662 731118597
21891 52301 761400909
14043 25071 761400909
8689 51151 761400909
35450 47080 731118597
40071 52093 761400909
4965 25822 761400909
5455 43403 761400909
4757 ...

output:

1816908497687

result:

ok single line: '1816908497687'

Test #22:

score: 0
Accepted
time: 67ms
memory: 30696kb

input:

100000 200000
20716 39671 556451313
12294 78769 797371104
49160 83948 797371104
11066 46096 556451313
9984 14047 556451313
26665 96682 797371104
33786 57807 797371104
8437 46537 556451313
80739 82677 797371104
32977 44465 797371104
15432 52132 797371104
26789 56446 797371104
14136 71796 556451313
58...

output:

24091738280208

result:

ok single line: '24091738280208'

Test #23:

score: 0
Accepted
time: 61ms
memory: 15164kb

input:

100000 200000
25928 33429 464816221
14226 75256 264307694
23122 86006 148988136
22122 83704 694275436
19682 42494 88492193
24533 87510 551457680
39760 79578 505977133
6643 43826 317919378
64169 70620 666065227
1790 84017 193815421
77934 82050 586690330
12209 22995 887978968
51901 67066 275336649
718...

output:

-1

result:

ok single line: '-1'

Test #24:

score: 0
Accepted
time: 99ms
memory: 33772kb

input:

100000 199998
48247 56159 76713
42511 96677 600939278
31457 68809 223073490
61392 96378 99783107
48247 49702 46960
23266 84538 154933836
48247 91849 48883
19981 91664 180677711
23052 67496 181946367
6342 36591 491375938
965 7473 17677
19319 48247 98209
12313 41956 295089188
32416 96800 18787362
4824...

output:

99993603163162

result:

ok single line: '99993603163162'

Test #25:

score: 0
Accepted
time: 64ms
memory: 30876kb

input:

100000 199998
6288 53595 38827
9879 78536 680644785
9879 93583 402853193
1133 4917 17087
9879 40885 465109629
9879 86997 486551034
9879 80756 165928883
42445 60933 83204
9879 50231 445828859
9879 61796 168230460
9879 18015 8016294
9879 30346 826496555
11598 51022 76116
9879 74311 495625753
9879 9985...

output:

66738232543176

result:

ok single line: '66738232543176'

Test #26:

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

input:

17 250
6 13 630447936
8 16 878869739
1 2 281730105
16 17 13236857
3 17 143829368
1 10 82971745
7 15 699622056
12 13 874287970
2 3 591935164
16 17 731693759
10 17 181631206
11 13 63955266
2 8 766963507
2 14 76956444
3 8 829602243
7 8 159867079
4 15 245367213
3 16 301598634
5 10 100293945
1 2 98432943...

output:

966708193

result:

ok single line: '966708193'

Test #27:

score: 0
Accepted
time: 71ms
memory: 33648kb

input:

100000 199998
76473 87318 568495206
81566 92905 87205516
7054 54594 674331001
84491 86442 512853146
33624 69155 90857
33624 61652 18127
33624 53030 28458
7054 69937 994281188
33624 89730 12149
14873 33624 9385
7054 49078 226456785
33624 40735 61499
20544 22284 582328703
7054 7236 893762795
20463 677...

output:

99985316115958

result:

ok single line: '99985316115958'

Test #28:

score: 0
Accepted
time: 94ms
memory: 32956kb

input:

100000 199998
16467 39554 79498
9387 10210 735712660
28499 70763 185276489
52434 55926 99345
11817 47988 950085064
45404 98116 45598
77459 89283 910410945
47106 47621 257849362
39447 81222 23019
13949 44510 393598870
30968 71915 292385920
48954 54113 96626
81569 87217 93280
28413 48773 48781
7576 45...

output:

99962908122796

result:

ok single line: '99962908122796'

Test #29:

score: 0
Accepted
time: 34ms
memory: 14008kb

input:

5178 200000
663 1474 863400607
606 1291 988233991
2060 2534 890386841
533 4532 653258418
335 586 585686861
1601 4115 499247959
162 3825 486122420
1851 4741 353185540
593 745 835155194
4142 4325 228619212
243 3053 193373928
1469 3799 75643075
1697 5108 157704718
1568 3491 392085260
1785 4835 31202296...

output:

176256487390

result:

ok single line: '176256487390'

Test #30:

score: 0
Accepted
time: 49ms
memory: 11704kb

input:

38799 200000
9536 37560 279767781
8091 21829 262724511
23642 31384 502303699
29872 35598 264556308
16522 27823 580185359
10462 28304 23142959
27133 34086 109324598
6117 33622 571210699
15150 29547 453590976
28322 28459 902992799
177 26315 982090673
11044 30247 861177220
14791 30425 782201551
20812 3...

output:

-1

result:

ok single line: '-1'

Test #31:

score: 0
Accepted
time: 20ms
memory: 11184kb

input:

10406 100000
1109 4265 850151342
4032 6478 850151342
481 1301 850151342
4892 7560 850151342
1370 4692 850151342
319 4249 850151342
8031 8443 359225769
6794 8252 850151342
1399 2010 850151342
5320 6025 850151342
4302 5041 850151342
3540 6915 850151342
1873 2005 850151342
2241 3988 850151342
7375 8493...

output:

5108080597470

result:

ok single line: '5108080597470'

Test #32:

score: 0
Accepted
time: 50ms
memory: 10860kb

input:

29678 200000
10319 12615 930321346
5168 8790 777188797
7256 9243 340490009
18200 24171 88062591
4734 6719 618255666
1530 29221 119464362
788 5971 858275043
11370 16513 351557562
19047 20176 5703782
5654 6266 871674180
1173 20855 879962688
5898 11808 172890260
4863 21512 478011356
2158 11290 94339226...

output:

-1

result:

ok single line: '-1'

Test #33:

score: 0
Accepted
time: 47ms
memory: 27368kb

input:

59777 119552
56673 57939 4385
11332 56673 38024
12173 50652 345732605
13742 20255 6428
17962 29673 377824942
55617 56673 1256
45235 56673 17175
42980 56673 22433
22418 56673 27858
11885 44781 970502031
35043 53493 934378971
15149 56673 37932
3163 48335 278941307
11714 13257 104115779
20255 29743 271...

output:

59774075354532

result:

ok single line: '59774075354532'

Test #34:

score: 0
Accepted
time: 50ms
memory: 15512kb

input:

14961 200000
1690 5670 130003145
5004 5540 696393947
6910 13608 118754932
9234 12719 841347907
60 6572 719795265
3903 8010 158076162
10057 12876 259688594
6387 7604 702341527
2093 13851 948154448
1496 5166 753386047
1459 5394 52839081
1096 11803 154519300
7555 7891 958623347
2075 6099 279192690
1380...

output:

1517661706169

result:

ok single line: '1517661706169'