QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#349098 | #6560. Broken Minimum Spanning Tree | realcomplex0# | WA | 13ms | 3848kb | C++20 | 1.8kb | 2024-03-09 23:36:57 | 2024-03-09 23:36:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
struct edge{
int uu;
int vv;
int ww;
int id;
bool operator< (const edge &ee) const {
return ww < ee.ww;
}
};
const int N = 2050;
int par[N];
int fin(int u){
if(par[u] == u) return u;
return par[u]=fin(par[u]);
}
bool unite(int u, int v){
u=fin(u);
v=fin(v);
if(u==v)return false;
par[u]=v;
return true;
}
int n;
void init(){
for(int i = 1; i <= n; i ++ ) par[i] = i;
}
int main(){
fastIO;
int m;
cin >> n >> m;
int u, v, w;
vector<edge> ee;
for(int i = 1; i <= m; i ++) {
cin >> u >> v >> w;
ee.push_back({u, v, w, i});
}
sort(ee.begin(), ee.end());
int good = 0;
vector<edge> cum;
vector<int> ao, bo;
for(int i = 0 ; i < ee.size(); i ++ ){
cum.push_back(ee[i]);
if(i + 1 == ee.size() || ee[i].ww != ee[i + 1].ww){
init();
for(int j = 0 ; j < i ; j ++ ){
if(ee[j].ww < ee[i].ww){
unite(ee[j].uu, ee[j].vv);
}
}
for(auto f : cum){
if(f.id <= n - 1 && !unite(f.uu, f.vv)){
ao.push_back(f.id); // remove f.uu
}
}
for(auto f : cum){
if(f.id >= n && unite(f.uu, f.vv)){
bo.push_back(f.id);
}
}
cum.clear();
}
}
cout << ao.size() << "\n";
for(int i = 0 ; i < ao.size(); i ++ ){
cout << ao[i] << " " << bo[i] << "\n";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3848kb
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: 1ms
memory: 3492kb
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 2 7 5 8
result:
ok correct!
Test #3:
score: 0
Accepted
time: 13ms
memory: 3684kb
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: 11ms
memory: 3680kb
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: 9ms
memory: 3632kb
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: 3840kb
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: 3508kb
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: 1ms
memory: 3808kb
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 173 672 158 657 159 658 160 659 161 660 162 661 163 662 164 663 165 664 166 665 167 666 168 667 169 668 170 669 171 670 172 671 157 656 174 673 175 674 176 675 177 676 178 677 179 678 180 679 181 680 182 681 183 682 184 683 185 684 186 685 187 686 188 687 142 641 127 626 128 627 129 628 130 629 ...
result:
wrong answer not a spanning tree after swap 1