QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #1513 | #881587 | #9904. 最小生成树 | TulipeNoire | SapnapTT | Success! | 2025-02-04 17:09:45 | 2025-02-04 17:09:45 |
詳細信息
Extra Test:
Wrong Answer
time: 56ms
memory: 7480kb
input:
200000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
19158529139
result:
wrong answer 1st numbers differ - expected: '17352503335', found: '19158529139'
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #881587 | #9904. 最小生成树 | SapnapTT | 97 | 62ms | 7812kb | C++20 | 709b | 2025-02-04 16:48:08 | 2025-02-04 17:21:05 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,t,T,f[N];
struct S{
int v,d;
friend bool operator<(S x,S y){
return x.v==y.v?x.d>y.d:x.v<y.v;
}
}a[N];
inline int F(int x){
return (f[x]==x?x:f[x]=F(f[x]));
}
long long A;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=3;i<=2*n-1;cin>>a[i].v,a[i].d=i,++i);
sort(a+3,a+2*n);
for(int i=1;i<=n;f[i]=i,++i);
for(int i=3,G;i<=2*n-1;++i){
for(int j=max(1,a[i].d-n),x,y,G=0;j<a[i].d-j;++j){
x=F(j),y=F(a[i].d-j);
if(x!=y) f[x]=y,A+=a[i].v,t++;
else G++;
T++;
if(t==n-1||(T>300000&&G>20)) break;
}
if(t==n-1) break;
}
cout<<A;
return 0;
}