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.

Download