- 隧道建设( svemir )
TLE!!!Why?
- 2023-3-25 12:55:41 @
#include"bits/stdc++.h"
using namespace std;
#define xx long long
xx r(){
xx x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct nd{xx x,y,z,uid;}a[100001];
struct eg{xx k,l,len;}b[300001];
int n=r(),m,g[100001],ii,Ans;
bool c1(nd a,nd b){return a.x<b.x;}
bool c2(nd a,nd b){return a.y<b.y;}
bool c3(nd a,nd b){return a.z<b.z;}
bool c4(eg a,eg b){return a.len<b.len;}
xx leng(nd a,nd b){return min(min(abs(a.x-b.x),abs(a.y-b.y)),abs(a.z-b.z));}
xx geng(int x){return(g[x]==x)?(x):(geng(g[x]));}
main()
{
xx i,wx,wy;;eg L;
for(i=1;i<=n;++i){
a[i].x=r(),a[i].y=r(),a[i].z=r(),a[i].uid=i;g[i]=i;
}sort(a+1,a+n+1,c1);for(xx i=1;i<n;++i)b[++m]=(eg){
a[i].uid,a[i+1].uid,leng(a[i],a[1+i])
};sort(a+1,a+n+1,c2);for(xx i=1;i<n;++i)b[++m]=(eg){
a[i].uid,a[i+1].uid,leng(a[i],a[1+i])
};sort(a+1,a+n+1,c3);for(xx i=1;i<n;++i)b[++m]=(eg){
a[i].uid,a[i+1].uid,leng(a[i],a[1+i])
};sort(b+1,b+m+1,c4);
ii=1;
for(i=1;i<n;++ii){
L=b[ii];wx=geng(L.k),wy=geng(L.l);
if(wx!=wy){
g[wx]=wy;
++i;Ans+=L.len;
}
}
cout<<Ans;
}
为什么???求助!
信息
- ID
- 350
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 41
- 已通过
- 14
- 上传者