QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#721099 | #5548. Increase the Toll Fees | wjt# | AC ✓ | 99ms | 33772kb | C++14 | 2.6kb | 2024-11-07 15:14:33 | 2024-11-07 15:14:37 |
Judging History
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'