QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#524681 | #6560. Broken Minimum Spanning Tree | amirreza# | WA | 2ms | 3852kb | C++20 | 3.1kb | 2024-08-20 00:34:15 | 2024-08-20 00:34:15 |
Judging History
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