QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#349245 | #6560. Broken Minimum Spanning Tree | realcomplex0# | WA | 12ms | 3852kb | C++20 | 3.3kb | 2024-03-10 00:15:41 | 2024-03-10 00:15:43 |
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 = 3050;
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;
}
const int M = 3010;
int A[M], B[M];
vector<int> T[N];
int dep[N];
vector<int> ao;
vector<int> bo;
pii up[N];
void dfs(int u, int par){
for(auto x : T[u]){
if(x == par) continue;
dep[x]=dep[u]+1;
dfs(x, u);
}
}
int del[N];
int fa = -1, fb = -1;
void fin(int u, int pa){
for(auto x : T[u]){
if(x == pa) continue;
fin(x, u);
up[u]=min(up[u],up[x]);
}
if(del[u] != -1 && up[u].fi < dep[u]){
fa = del[u];
fb = up[u].se;
}
}
bool output = false;
void flip(){
for(int i = 1; i <= n; i ++) {
T[i].clear();
up[i] = mp((int)1e9, -1);
del[i] = -1;
}
for(int i = 1; i <= n - 1; i ++ ){
T[A[i]].push_back(B[i]);
T[B[i]].push_back(A[i]);
}
dfs(1,1);
for(auto x : bo){
if(x == -1) continue;
if(dep[A[x]] < dep[B[x]]) swap(A[x], B[x]); // A[x] is deep
up[A[x]]=min(up[A[x]], mp(dep[B[x]], x));
}
for(auto x : ao){
if(x == -1) continue;
if(dep[A[x]] < dep[B[x]]) swap(A[x], B[x]);
del[A[x]] = x;
}
fa = -1;
fb = -1;
fin(1, -1);
for(auto &x : ao){
if(x == fa) x = -1;
}
for(auto &x : bo){
if(x == fb) x = -1;
}
swap(A[fa], A[fb]);
swap(B[fa], B[fb]);
cout << fa << " " << fb << "\n";
}
int main(){
fastIO;
//freopen("in.txt", "r", stdin);
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});
A[i] = u;
B[i] = v;
}
sort(ee.begin(), ee.end());
int good = 0;
vector<edge> cum;
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);
}
}
for(auto f : cum){
if(f.id >= n && unite(f.uu, f.vv)){
bo.push_back(f.id);
}
}
cum.clear();
}
}
int sz = ao.size();
cout << sz << "\n";
for(int i = 0; i < sz; i ++ ) {
flip();
output=true;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3764kb
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: 3608kb
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: 12ms
memory: 3700kb
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: 3684kb
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: 12ms
memory: 3712kb
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: 0ms
memory: 3656kb
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: 0ms
memory: 3820kb
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: 0
Accepted
time: 3ms
memory: 3628kb
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 1 500 496 501 2 502 3 503 4 504 5 505 6 506 7 507 8 508 9 509 10 510 11 511 12 512 13 513 14 514 15 515 16 516 17 517 18 518 19 519 20 520 21 521 22 522 23 523 24 524 25 525 26 526 27 527 28 528 29 529 30 530 31 531 32 532 33 533 34 534 35 535 36 536 37 537 38 538 39 539 40 540 41 541 42 542 43 ...
result:
ok correct!
Test #9:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
500 998 198 227 1 227 315 1 315 426 1 426 400 1 400 61 1 61 143 1 143 487 1 487 65 1 65 415 1 415 434 1 434 327 1 327 190 1 190 411 1 411 51 1 51 91 1 91 364 1 364 185 1 185 393 1 393 89 1 89 53 1 53 66 1 66 69 1 69 13 1 13 5 1 5 45 1 45 314 1 314 291 1 291 490 1 490 92 1 92 175 1 175 458 1 458 218 ...
output:
0
result:
ok correct!
Test #10:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
500 998 360 250 1 250 71 1 71 170 1 170 492 1 492 419 1 419 145 1 145 188 1 188 433 1 433 186 1 186 161 1 161 398 1 398 19 1 19 479 1 479 401 1 401 40 1 40 176 1 176 212 1 212 353 1 353 290 1 290 43 1 43 322 1 322 447 1 447 47 1 47 468 1 468 456 1 456 343 1 343 339 1 339 52 1 52 251 1 251 130 1 130 ...
output:
0
result:
ok correct!
Test #11:
score: -100
Wrong Answer
time: 5ms
memory: 3712kb
input:
500 998 369 45 2 45 364 2 364 300 2 300 195 2 195 291 2 291 390 2 390 122 2 122 331 2 331 408 2 408 91 2 91 298 2 298 116 2 116 301 2 301 287 2 287 338 2 338 4 2 4 79 2 79 177 2 177 387 2 387 125 2 125 477 2 477 11 2 11 284 2 284 102 2 102 305 2 305 395 2 395 112 2 112 280 2 280 294 2 294 232 2 232 ...
output:
499 113 996 135 997 210 998 373 629 372 679 209 663 123 559 198 538 205 781 130 771 196 995 195 662 142 680 140 873 111 664 68 665 203 752 497 842 156 843 154 537 263 792 262 994 89 666 88 539 281 540 279 798 152 822 150 536 148 870 348 603 352 694 143 687 347 667 371 831 86 841 80 668 77 834 329 57...
result:
wrong answer Integer parameter [name=a] equals to -1, violates the range [1, 998]