VNEMPIRE - Đế chế
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
fo='';
maxn=100010;
type ar=array[0..maxn] of longint;
arr=array[0..2,0..maxn] of longint;
var n:longint;
nh:array[0..2] of longint;
a,b,c,x,y,z,par:ar;
d,h,v:arr;
re:int64;
procedure rf;
var i:longint;
begin
read(n);
for i:=1 to n do
begin
read(a[i],b[i],c[i]);
x[i]:=a[i]; y[i]:=b[i]; z[i]:=c[i];
d[0,i]:=i; d[1,i]:=i; d[2,i]:=i;
par[i]:=i;
end;
end;
procedure sort(var x:ar;z,l,r:longint);
var i,j,t,y:longint;
begin
i:=l; j:=r; t:=x[(i+j) shr 1];
repeat
while x[i]<t do i:=i+1;
while x[j]>t do j:=j-1;
if i<=j then
begin
y:=x[i]; x[i]:=x[j]; x[j]:=y;
y:=d[z,i]; d[z,i]:=d[z,j]; d[z,j]:=y;
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sort(x,z,i,r);
if l<j then sort(x,z,l,j);
end;
procedure add(z,x:longint);
var cha,con:longint;
begin
inc(nh[z]); con:=nh[z];
cha:=con shr 1;
while (cha>0) and (v[z,h[z,cha]]>v[z,x]) do
begin
h[z,con]:=h[z,cha];
con:=cha;
cha:=con shr 1;
end;
h[z,con]:=x;
end;
function pop(z:longint):longint;
var x,cha,con:longint;
begin
pop:=h[z,1];
x:=h[z,nh[z]]; dec(nh[z]);
cha:=1; con:=2;
while con<=nh[z] do
begin
if (con<nh[z]) and (v[z,h[z,con+1]]<v[z,h[z,con]]) then inc(con);
if v[z,x]<=v[z,h[z,con]] then break;
h[z,cha]:=h[z,con];
cha:=con;
con:=cha shl 1;
end;
h[z,cha]:=x;
end;
procedure init;
var i:longint;
begin
for i:=1 to n-1 do
begin
v[0,i]:=x[i+1]-x[i];
v[1,i]:=y[i+1]-y[i];
v[2,i]:=z[i+1]-z[i];
add(0,i);
add(1,i);
add(2,i);
end;
end;
function getmin:longint;
begin
if (v[0,h[0,1]]<=v[1,h[1,1]]) and (v[0,h[0,1]]<=v[2,h[2,1]]) then exit(0)
else
if v[1,h[1,1]]<=v[2,h[2,1]] then exit(1)
else exit(2);
end;
function find(x:longint):longint;
begin
if x=par[x] then exit(x)
else
begin
par[x]:=find(par[x]);
exit(par[x]);
end;
end;
procedure pr;
var i,t,u,p,q:longint;
begin
sort(x,0,1,n);
sort(y,1,1,n);
sort(z,2,1,n);
init;
for i:=1 to n-1 do
while true do
begin
t:=getmin;
u:=pop(t);
p:=find(d[t,u]); q:=find(d[t,u+1]);
if p<>q then
begin
re:=re+v[t,u];
par[q]:=p;
break;
end;
end;
writeln(re);
end;
begin
assign(input,fi); reset(input);
rf;
pr;
close(input);
end.