QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#524681#6560. Broken Minimum Spanning Treeamirreza#WA 2ms3852kbC++203.1kb2024-08-20 00:34:152024-08-20 00:34:15

Judging History

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

  • [2024-08-20 00:34:15]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3852kb
  • [2024-08-20 00:34:15]
  • 提交

answer


// ki bood ke goft Ghatinga?

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,int> ppiii;

// vectors and Sets:
#define vc vector
#define pb push_back
#define all(c) (c).begin(), (c).end()

// pairs
#define mp make_pair
#define fr first
#define sc second

// execution time check and Debug
#define StartEX clock_t startExeTime = clock();
#define EndEX clock_t endExeTime = clock();
#define ExTime cerr << "\nTotal Execution Time is: " << double(-double(startExeTime)+double(endExeTime)) / CLOCKS_PER_SEC;
#define debug(x) cerr << #x << " : " << x << '\n'
#define endl "\n"

// time optimization
#define Heh ios::sync_with_stdio(false);cin.tie(0);
#define Bah ios::sync_with_stdio(false);
#pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")

// useful functions
ll pw(ll a,ll b){
  ll ret = 1;
  ll mul = a;
  while(b > 0){
	if(b&1)
	  ret = (ret * mul);
	mul = (mul * mul);
	b >>= 1;
  }
  return ret;
}
ll pw(ll a,ll b,ll mod){
  ll ret = 1;
  ll mul = a;
  while(b > 0){
	if(b&1)
	  ret = (ret * mul) % mod;
	mul = (mul * mul) % mod;
	b >>= 1;
  }
  return ret;
}

ll to_int(string s){
  ll ret = 0;
  for(int i = 0 ; i < (int)s.size() ; i++) ret = 10 * ret + s[i] - '0';
  return ret;
}

bool deq(ld a , ld b){return (abs(a-b) < 0.000001);} // 10 ^ -6

const int MAXM = 3e3 + 33;

int n , m;

int par[MAXM] , rnk[MAXM];
int get(int v){return par[v] = (par[v] == v ? v : get(par[v]));}
void uni(int a , int b){
  a = get(a) , b = get(b);
  if(a == b) return;
  if(rnk[a] < rnk[b]) swap(a , b);
  par[b] = a;
  rnk[a] += (rnk[a] == rnk[b]);
}

struct ed{
  int u , v , w;
  int id;

  bool operator<(ed x){
    return w < x.w;
  }
};

int main()
{
  Heh;
  cin >> n >> m;
  ed es[m] , ses[m] , nes[m];
  for(int i = 0 ; i < m ; i++){
    int u , v , w;
    cin >> u >> v >> w;
    u-- , v--;
    es[i] = {u , v , w , i};
    ses[i] = es[i];
    nes[i] = es[i];
  }
  sort(es , es + n-1);
  sort(ses , ses + m);
  vc<int> add , rem;

  for(int i = 0 ; i < n ; i++) par[i] = i , rnk[i] = 0;
  int pt1 = 0 , pt2 = 0;
  vc<pii> bs;
  while(pt1 < n-1 or pt2 < m){
    if(pt2 == m or (pt1 < n-1 and es[pt1].w <= ses[pt2].w)){
      if(get(es[pt1].u) == get(es[pt1].v)){
	rem.pb(es[pt1].id);
      }
      else{
	uni(es[pt1].u , es[pt1].v);
	bs.pb({es[pt1].u , es[pt1].v});
      }
      pt1++;
    }
    else{
      if(get(ses[pt2].u) != get(ses[pt2].v)){
	add.pb(ses[pt2].id);
	uni(ses[pt2].u , ses[pt2].v);
      }
      pt2++;
    }
  }
  cout << add.size() << endl;
  for(int ri : rem){
    for(int i = 0 ; i < n ; i++) par[i] = i , rnk[i] = 0;
    for(auto [u , v] : bs) uni(u , v);

    uni(nes[ri].u , nes[ri].v);
    int sai = -1;
    for(int ai : add){
      if(get(nes[ai].u) == get(nes[ai].v)){
	cout << ri+1 << " " << ai+1 << endl;
	sai = ai;
	break;
      }
      uni(nes[ai].u , nes[ai].v);
    }

    vc<int> nadd;
    for(int ai : add){
      if(ai != sai) nadd.pb(ai);
    }
    add = nadd;
  }
}

// ki seda kard Patinga?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3760kb

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: 3496kb

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: 1ms
memory: 3704kb

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: 1ms
memory: 3712kb

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: 3692kb

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: 3552kb

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: 3668kb

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: 3852kb

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
328 828
343 843
342 842
341 841
340 840
339 839
338 838
337 837
336 836
335 835
334 834
333 833
332 832
331 831
330 830
329 829
344 844
327 827
326 826
325 825
324 824
323 823
322 822
321 821
320 820
319 819
318 818
317 817
316 816
315 815
314 814
313 813
359 859
374 874
373 873
372 872
371 871
...

result:

wrong output format Unexpected end of file - int32 expected