QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#721834 | #5548. Increase the Toll Fees | KeeperHihi# | TL | 553ms | 18248kb | C++20 | 2.5kb | 2024-11-07 16:58:11 | 2024-11-07 16:58:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
struct DSU {
vector<int> f, siz;
vector<vector<int>> pos;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n + 1);
iota(f.begin(), f.end(), 0);
siz.assign(n + 1, 1);
pos.assign(n + 1, {});
}
int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
if (pos[x].size() < pos[y].size()) {
swap(pos[x], pos[y]);
}
for (auto idx : pos[y]) {
pos[x].emplace_back(idx);
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<tuple<int, int, int>> edge;
vector<int> vis(m);
vector<int> y;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
if (a > b) swap(a, b);
edge.emplace_back(c, a, b);
y.emplace_back(c);
}
sort(y.begin(), y.end());
y.resize(unique(y.begin(), y.end()) - y.begin());
for (auto &[w, u, v] : edge) {
w = lower_bound(y.begin(), y.end(), w) - y.begin();
}
sort(edge.begin(), edge.end());
DSU dsu(n);
for (int i = 0; i < m; i++) {
auto [w, u, v] = edge[i];
if (dsu.same(u, v)) {
continue;
}
vis[i] = 1;
dsu.merge(u, v);
}
dsu.init(n);
int ans = 0;
for (int i = 0; i < m; i++) {
if (vis[i]) {
auto [w, u, v] = edge[i];
ans -= y[w];
}
}
unordered_set<int> set;
for (int i = 0; i < m; i++) {
auto [w, u, v] = edge[i];
u = dsu.find(u);
v = dsu.find(v);
if (vis[i]) {
dsu.pos[u].emplace_back(i);
continue;
}
if (dsu.same(u, v)) continue;
dsu.merge(u, v);
vector<int> nex;
for (auto idx : dsu.pos[u]) {
auto [a, u, v] = edge[idx];
if (dsu.same(u, v)) {
ans += y[w] + 1;
} else {
nex.emplace_back(idx);
}
}
swap(dsu.pos[u], nex);
}
if (dsu.size(1) != n) {
cout << "-1\n";
return;
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
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: 0ms
memory: 3620kb
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: 0ms
memory: 3824kb
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: 0ms
memory: 3572kb
input:
2 1 1 2 1
output:
-1
result:
ok single line: '-1'
Test #5:
score: 0
Accepted
time: 405ms
memory: 9656kb
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: 553ms
memory: 14512kb
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: 24ms
memory: 9012kb
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: 267ms
memory: 14492kb
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: 327ms
memory: 8988kb
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: 154ms
memory: 14724kb
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: 41ms
memory: 11744kb
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: 149ms
memory: 17492kb
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: 84ms
memory: 15892kb
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: 78ms
memory: 18248kb
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: 0ms
memory: 3564kb
input:
2 2 1 2 1 1 2 1000000000
output:
1000000000
result:
ok single line: '1000000000'
Test #16:
score: 0
Accepted
time: 110ms
memory: 16888kb
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: 82ms
memory: 13376kb
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: -100
Time Limit Exceeded
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...