QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#721447 | #5548. Increase the Toll Fees | KeeperHihi# | TL | 32ms | 12212kb | C++20 | 3.0kb | 2024-11-07 16:07:55 | 2024-11-07 16:07:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
struct DSU {
vector<int> f, siz;
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);
}
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;
}
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());
// for (auto [w, u, v] : edge) {
// cout << u << ' ' << v << ' ' << w << endl;
// }
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);
}
// for (int i = 0; i < m; i++) {
// cout << vis[i] << " \n"[i + 1 == m];
// }
dsu.init(n);
vector<vector<int>> tong(m + 1);
for (int i = 0; i < m; i++) {
auto [w, u, v] = edge[i];
tong[w].emplace_back(i);
}
int ans = 0;
// for (int i = 0; i < m; i++) {
// cout << y[i] << " \n"[i + 1 == m];
// }
for (int i = 0; i < m; i++) {
// cout << "i = " << i << endl;
// for (int j = 0; j < m; j++) {
// cout << "j = " << j << " : ";
// for (auto t : tong[j]) {
// cout << t << ' ';
// }
// cout << endl;
// }
vector<int> cur;
for (auto idx : tong[i]) {
auto [w, u, v] = edge[idx];
if (vis[idx]) {
cur.emplace_back(idx);
} else {
if (!dsu.same(u, v)) {
dsu.merge(u, v);
}
}
}
vector<int> nex;
// for (auto t : cur) cout << t << ' '; cout << endl;
for (auto idx : cur) {
auto [w, u, v] = edge[idx];
if (dsu.same(u, v)) {
// cout << "hello : " << y[i] << ' ' << w << endl;
ans += y[i] + 1 - y[w];
} else {
nex.emplace_back(idx);
}
}
if (nex.size() > tong[i + 1].size()) {
swap(nex, tong[i + 1]);
}
for (auto t : nex) {
tong[i + 1].emplace_back(t);
}
// cout << "ans = " << ans << endl;
}
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: 3612kb
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: 3616kb
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: 3556kb
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: 3616kb
input:
2 1 1 2 1
output:
-1
result:
ok single line: '-1'
Test #5:
score: 0
Accepted
time: 32ms
memory: 12212kb
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: -100
Time Limit Exceeded
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...