QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#349245#6560. Broken Minimum Spanning Treerealcomplex0#WA 12ms3852kbC++203.3kb2024-03-10 00:15:412024-03-10 00:15:43

Judging History

你现在查看的是最新测评结果

  • [2024-03-10 00:15:43]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:3852kb
  • [2024-03-10 00:15:41]
  • 提交

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]