QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#241008 | #6560. Broken Minimum Spanning Tree | MovingUp# | WA | 2ms | 3476kb | C++14 | 3.1kb | 2023-11-05 21:52:24 | 2023-11-05 21:52:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct edge {
int id;
int u, v, w;
bool operator<(const edge &o) const {
if (w == o.w) {
return id < o.id;
}
return w < o.w;
}
};
struct dsu {
vector<int> parent, subtree;
void init(int n) {
parent.resize(n);
subtree.resize(n);
for (int i = 0; i < n; i++) {
subtree[i] = 1;
parent[i] = i;
}
}
int findParent(int x) {
if (parent[x] == x)
return x;
else {
parent[x] = findParent(parent[x]);
return parent[x];
}
}
void unite(int parX, int parY) {
if (subtree[parX] < subtree[parY]) {
parent[parX] = parY;
subtree[parY] += subtree[parX];
} else {
parent[parY] = parX;
subtree[parX] += subtree[parY];
}
}
};
int64_t findMst(int n, const vector<edge> &edges, int edgeId) {
dsu d;
d.init(n);
int64_t ans = 0;
for (auto e : edges) {
if (e.id == edgeId) {
ans += e.w;
d.unite(e.u, e.v);
}
}
for (auto e : edges) {
if (e.id == edgeId) {
continue;
}
int parX = d.findParent(e.u);
int parY = d.findParent(e.v);
if (parX != parY) {
ans += e.w;
d.unite(parX, parY);
}
}
return ans;
}
int findReplacement(int n, const vector<edge> &edges, vector<bool>& forced) {
dsu d;
d.init(n);
for (auto e : edges) {
if (forced[e.id]) {
d.unite(e.u, e.v);
}
}
for (auto e : edges) {
if (forced[e.id]) {
continue;
}
int parX = d.findParent(e.u);
int parY = d.findParent(e.v);
if (parX != parY) {
return e.id;
}
}
assert(false);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<edge> edges(m);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
u--;
v--;
edges[i] = {i, u, v, w};
}
sort(edges.begin(), edges.end());
int64_t globalMst = findMst(n, edges, -1);
vector<bool> keep(n - 1, false);
{
dsu d;
d.init(n);
int64_t ans = 0;
for (auto e : edges) {
int parX = d.findParent(e.u);
int parY = d.findParent(e.v);
if (parX != parY) {
ans += e.w;
d.unite(parX, parY);
if (e.id < n - 1) {
keep[e.id] = true;
}
}
}
}
vector<bool> forced(m);
vector<int> removals;
for (int i = 0; i < n - 1; i++) {
forced[i] = true;
if (!keep[i]) {
removals.push_back(i);
}
}
vector<pair<int, int>> changes;
while (!removals.empty()) {
int id = removals.back();
removals.pop_back();
forced[id] = false;
int replacement = findReplacement(n, edges, forced);
forced[replacement] = true;
changes.push_back({id, replacement});
}
int64_t newMst = 0;
for (int i = 0; i < m; i++) {
edge e = edges[i];
if (forced[e.id]) {
newMst += e.w;
}
}
// if (newMst != globalMst) {
// assert(false);
// }
cout << changes.size() << endl;
for (auto [x, y] : changes) {
cout << x + 1 << " " << y + 1 << endl;
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3464kb
input:
4 4 1 2 10 2 3 3 3 4 1 1 4 4
output:
1 1 4
result:
ok correct!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
6 8 1 2 10 2 3 10 3 4 10 4 5 10 5 6 10 6 1 10 1 3 1 4 6 1
output:
2 5 8 2 7
result:
ok correct!
Test #3:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
2000 1999 1262 1505 968661582 323 1681 787089412 1132 129 88786681 1909 587 762050278 979 1371 230688681 1686 521 980519364 975 191 887826021 869 461 899130441 1433 259 961154249 1718 547 721696188 1254 1042 458319755 1779 267 85751052 1170 813 283230029 309 20 971682908 224 417 255325364 1084 986 7...
output:
0
result:
ok correct!
Test #4:
score: 0
Accepted
time: 0ms
memory: 3448kb
input:
1999 1998 1757 1820 444157563 1757 395 754598547 1757 1571 432619009 1757 1009 456234067 1757 824 935569725 1757 1698 476714469 1757 1420 901765343 1757 1175 225295107 1757 1512 721959801 1757 1585 955067704 1757 1739 635181418 1757 1686 891225461 1757 84 132683224 1757 1696 48915557 1757 1623 42602...
output:
0
result:
ok correct!
Test #5:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
1999 1998 1345 647 232183406 40 837 279910457 819 857 137486924 255 1378 517489941 827 1565 894953662 1556 1545 898170464 965 877 72248541 1631 298 635713424 895 197 366305735 966 1160 515776809 1870 1638 220711661 1736 220 716014108 1914 1609 759121968 1293 153 272816132 1936 1433 263859075 985 460...
output:
0
result:
ok correct!
Test #6:
score: 0
Accepted
time: 1ms
memory: 3448kb
input:
500 998 105 1 1 105 2 1 105 3 1 105 4 1 105 5 1 105 6 1 105 7 1 105 8 1 105 9 1 105 10 1 105 11 1 105 12 1 105 13 1 105 14 1 105 15 1 105 16 1 105 17 1 105 18 1 105 19 1 105 20 1 105 21 1 105 22 1 105 23 1 105 24 1 105 25 1 105 26 1 105 27 1 105 28 1 105 29 1 105 30 1 105 31 1 105 32 1 105 33 1 105 ...
output:
0
result:
ok correct!
Test #7:
score: 0
Accepted
time: 1ms
memory: 3392kb
input:
500 998 364 1 1 364 2 1 364 3 1 364 4 1 364 5 1 364 6 1 364 7 1 364 8 1 364 9 1 364 10 1 364 11 1 364 12 1 364 13 1 364 14 1 364 15 1 364 16 1 364 17 1 364 18 1 364 19 1 364 20 1 364 21 1 364 22 1 364 23 1 364 24 1 364 25 1 364 26 1 364 27 1 364 28 1 364 29 1 364 30 1 364 31 1 364 32 1 364 33 1 364 ...
output:
0
result:
ok correct!
Test #8:
score: -100
Wrong Answer
time: 2ms
memory: 3460kb
input:
500 998 86 1 2 86 2 2 86 3 2 86 4 2 86 5 2 86 6 2 86 7 2 86 8 2 86 9 2 86 10 2 86 11 2 86 12 2 86 13 2 86 14 2 86 15 2 86 16 2 86 17 2 86 18 2 86 19 2 86 20 2 86 21 2 86 22 2 86 23 2 86 24 2 86 25 2 86 26 2 86 27 2 86 28 2 86 29 2 86 30 2 86 31 2 86 32 2 86 33 2 86 34 2 86 35 2 86 36 2 86 37 2 86 38...
output:
499 499 998 498 997 497 996 496 500 495 501 494 502 493 503 492 504 491 505 490 506 489 507 488 508 487 509 486 510 485 511 484 512 483 513 482 514 481 515 480 516 479 517 478 518 477 519 476 520 475 521 474 522 473 523 472 524 471 525 470 526 469 527 468 528 467 529 466 530 465 531 464 532 463 533 ...
result:
wrong answer not a spanning tree after swap 5