Editorial for Đế chế
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
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.
Code mẫu của happyboy99x
#include<cstdio> #include<algorithm> using namespace std; const int N = 100000 + 2; struct empire { int x, y, z, id; int distance(const empire &o) { return min(abs(x - o.x), min(abs(y - o.y), abs(z - o.z))); } } a[N]; bool x_cmp(const empire &a, const empire &b) { return a.x < b.x; } bool y_cmp(const empire &a, const empire &b) { return a.y < b.y; } bool z_cmp(const empire &a, const empire &b) { return a.z < b.z; } struct edge { int u, v, d; bool operator < (const edge &o) const { return d < o.d; } edge() {} edge(int u, int v, int d): u(u), v(v), d(d) {} } e[3*N]; int p[N], n; void initSet(int n) { for(int i = 0; i < n; ++i) p[i] = i; } int getSet(int u) { return p[u] == u ? u : p[u] = getSet(p[u]); } void enter() { scanf("%d", &n); for(int i = 0; i < n; ++i) { scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z); a[i].id = i; } } void addEdge(int &nEdge) { for(int i = 1; i < n; ++i) e[nEdge++] = edge(a[i].id, a[i-1].id, a[i-1].distance(a[i])); } void solve() { int nEdge = 0; sort(a, a+n, x_cmp); addEdge(nEdge); sort(a, a+n, y_cmp); addEdge(nEdge); sort(a, a+n, z_cmp); addEdge(nEdge); sort(e, e + nEdge); initSet(n); long long res = 0; for(int cnt = 0, i = 0; cnt != n-1; ++i) if(getSet(e[i].u) != getSet(e[i].v)) res += e[i].d, p[p[e[i].u]] = p[e[i].v], ++cnt; printf("%lld\n", res); } int main() { enter(); solve(); return 0; }
Code mẫu của ladpro98
{$MODE OBJFPC} program vnempire; uses math; const maxn=100005; maxm=6*maxn; fi=''; type e=record x,y,w:longint; end; point =record v,p:longint; end; arr=array[1..maxn] of point; var x,y,z:arr; inp:text; n,m,k,res,i,xx,yy:longint; ed:array[1..maxm] of e; lab:array[1..maxn] of longint; procedure sort(var a:arr; l,r:longint); var p,i,j:longint; t:point; begin if l>=r then exit; i:=l;j:=r; p:=a[random(r-l+1)+l].v; repeat while a[i].v<p do inc(i); while a[j].v>p do dec(j); if i<=j then begin if i<j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; inc(i);dec(j); end; until i>j; sort(a,l,j);sort(a,i,r); end; procedure sortE(l,r:longint); var p,i,j:longint; t:e; begin if l>=r then exit; i:=l;j:=r; p:=ed[random(r-l+1)+l].w; repeat while ed[i].w<p do inc(i); while ed[j].w>p do dec(j); if i<=j then begin if i<j then begin t:=ed[i]; ed[i]:=ed[j]; ed[j]:=t; end; inc(i); dec(j); end; until i>j; sortE(l,j);sortE(i,r); end; function root(u:longint):longint; begin if lab[u]<=0 then exit(u); result:=root(lab[u]); lab[u]:=result; end; procedure union(u,v:longint); begin if lab[u]<lab[v] then lab[v]:=u else begin if lab[u]=lab[v] then dec(lab[v]); lab[u]:=v; end; end; begin assign(inp,fi);reset(inp); readln(inp,n); for i:=1 to n do begin readln(inp,x[i].v,y[i].v,z[i].v); x[i].p:=i;y[i].p:=i;z[i].p:=i; end; sort(x,1,n);sort(y,1,n);sort(z,1,n); for i:=2 to n do begin inc(m); ed[m].x:=x[i].p;ed[m].y:=x[i-1].p;ed[m].w:=abs(x[i].v-x[i-1].v); inc(m); ed[m].x:=y[i].p;ed[m].y:=y[i-1].p;ed[m].w:=abs(y[i].v-y[i-1].v); inc(m); ed[m].x:=z[i].p;ed[m].y:=z[i-1].p;ed[m].w:=abs(z[i].v-z[i-1].v); end; sortE(1,m); for i:=1 to m do begin xx:=root(ed[i].x); yy:=root(ed[i].y); if xx<>yy then begin union(xx,yy); inc(res,ed[i].w); inc(k); end; if k=n-1 then break; end; write(res); end.
Code mẫu của RR
#include <iostream> #include <algorithm> #include <vector> #include <set> #define MAXN 100111 #define oo 1000111000 #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define FORV(i,v) for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++) #define P pair<int,int> #define F first #define S second #define MP make_pair #define PB push_back using namespace std; int debug=0; int n,a[MAXN][3],d[MAXN]; vector< P > ke[MAXN]; P c[MAXN]; void inp() { scanf("%d",&n); FOR(i,1,n) FOR(j,0,2) scanf("%d",&a[i][j]); } void init() { FOR(j,0,2) { FOR(i,1,n) { c[i].F=a[i][j]; c[i].S=i; } sort(c+1,c+n+1); FOR(i,1,n) { if (i>1) ke[c[i].S].PB(MP(c[i-1].S,c[i].F-c[i-1].F)); if (i<n) ke[c[i].S].PB(MP(c[i+1].S,c[i+1].F-c[i].F)); } } if (debug) FOR(i,1,n) { FORV(now,ke[i]) cout<<"("<<now->F<<","<<now->S<<") "; cout<<endl; } } set< P > s; void modify(int i) { FORV(now,ke[i]) { int j=now->F, c=now->S; if (d[j]<0) continue; if (c<d[j]) { d[j]=c; s.insert(MP(c,j)); } } } void solve() { FOR(i,1,n) d[i]=oo; modify(1); d[1]=-1; long long res=0; while (!s.empty()) { set< P >::iterator it=s.begin(); int c=it->F, j=it->S; s.erase(it); if (c!=d[j]) continue; if (d[j]<0) continue; d[j]=-1; modify(j); res+=c; } cout<<res; } int main() { inp(); init(); solve(); return 0; }
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(__typeof(n) i = 0; i < (n); ++i) #define Repd(i,n) for(__typeof(n) i = (n)-1; i >= 0; --i) #define For(i,a,b) for(__typeof(b) i = (a); i <= (b); ++i) #define Ford(i,a,b) for(__typeof(a) i = (a); i >= (b); --i) #define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) #define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) #define nl puts("") #define sp printf(" ") #define ok puts("ok") //#include <conio.h> template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} }; template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template<class T> bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } const double PI = 2 * acos(0); const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"}; const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; //const int dr[] = {0, 0, -1, +1}; //const int dc[] = {-1, +1, 0, 0}; const int dr[] = {-2, -1, +1, +2, +2, +1, -1, -2}; const int dc[] = {+1, +2, +2, +1, -1, -2, -2, -1}; const int inf = (int)1e9 + 5; const ll linf = (ll)1e16 + 5; const double eps = 1e-9; const ll mod = 1000000000; typedef pair<int, int> II; using namespace std; #define maxn 300005 struct graph{ int x,y,cost; graph(){}; graph(int _x, int _y, int _cost){ x = _x; y = _y; cost = _cost; } bool operator <(graph const G) const{ return cost<G.cost; } }; graph v[maxn]; int par[maxn]; int find(int x){ if(x == par[x]) return x; return par[x] = find(par[x]); } bool Union(int a,int b){ int p = find(a); int q = find(b); if(p == q) return false; par[p] = max(p, q); par[q] = max(p, q); return true; } pair<Triple<int>, int> A[maxn]; bool comx(pair<Triple<int>, int> const &T1, pair<Triple<int>, int> const &T2){ return T1.fi.x < T2.fi.x;} bool comy(pair<Triple<int>, int> const &T1, pair<Triple<int>, int> const &T2){ return T1.fi.y < T2.fi.y;} bool comz(pair<Triple<int>, int> const &T1, pair<Triple<int>, int> const &T2){ return T1.fi.z < T2.fi.z;} int dis(pair<Triple<int>, int> const T1, pair<Triple<int>, int> const T2){ return min(abs(T1.fi.x - T2.fi.x), min( abs(T1.fi.y - T2.fi.y), abs(T1.fi.z - T2.fi.z))); } int main(){ // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int n; gi(n); Rep(i, n) { gi(A[i].fi.x); gi(A[i].fi.y); gi(A[i].fi.z); A[i].se = i; } sort(A, A + n, comx); int num = 0; Rep(i, n + 1) par[i] = i; Rep(i, n - 1){ v[num++] = graph(A[i].se, A[i + 1].se, dis(A[i], A[i + 1])); } sort(A, A + n, comy); Rep(i, n - 1){ v[num++] = graph(A[i].se, A[i + 1].se, dis(A[i], A[i + 1])); } sort(A, A + n, comz); Rep(i, n - 1){ v[num++] = graph(A[i].se, A[i + 1].se, dis(A[i], A[i + 1])); } sort(v, v + num); ll res = 0; Rep(i, num){ if(Union(v[i].x, v[i].y)){ res += v[i].cost; } } cout << res << endl; // getch(); }
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <cstring> #include <deque> #include <fstream> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> typedef long long ll; using namespace std; struct edge { int u,v,cost; }; int n; int x[100010],y[100010],z[100010]; int pre[100010]; int lab[100010]; vector< pair<int,int> > v; vector<edge> e; bool cmp(edge q1,edge q2) { return (q1.cost < q2.cost); }; void addedge() { sort(v.begin(),v.end()); for (int i = 1; i < v.size(); i++) { edge new_edge; new_edge.u = v[i - 1].second; new_edge.v = v[i].second; new_edge.cost = v[i].first - v[i - 1].first; e.push_back(new_edge); }; v.clear(); }; void makeset(int k) { pre[k] = k; lab[k] = 0; }; int root(int k) { if (k != pre[k]) pre[k] = root(pre[k]); return pre[k]; }; void connect(int i,int j) { int i1 = root(i),j1 = root(j); if (lab[i1] > lab[j1]) pre[j1] = i1; else pre[i1] = j1; if (lab[i1] == lab[j1]) lab[j1]++; }; int main() { // freopen("empire.in","r",stdin); // freopen("empire.ou","w",stdout); scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d %d %d", &x[i], &y[i], &z[i]); for (int i = 1; i <= n; i++) v.push_back(make_pair(x[i],i)); addedge(); for (int i = 1; i <= n; i++) v.push_back(make_pair(y[i],i)); addedge(); for (int i = 1; i <= n; i++) v.push_back(make_pair(z[i],i)); addedge(); sort(e.begin(),e.end(),cmp); for (int i = 1; i <= n; i++) makeset(i); ll ret = 0; for (int i = 0; i < e.size(); i++) if (root(e[i].u) != root(e[i].v)) { connect(e[i].u,e[i].v); ret += e[i].cost; }; cout << ret << endl; };
Code mẫu của khuc_tuan
#include <iostream> #include <cstdio> #include <vector> #include <map> #include <set> #include <queue> #include <algorithm> #include <cstring> #include <cmath> using namespace std; #define Rep(i,n) for(int i=0;i<(n);++i) #define For(i,a,b) for(int i=(a);i<=(b);++i) #define Ford(i,a,b) for(int i=(a);i>=(b);--i) #define fi first #define se second #define pb push_back #define MP make_pair int x[100010],y[100010],z[100010]; int n, ne; pair<int,int> a[100010],b[100010],c[100010]; pair<int,pair<int,int> > e[300010]; int f[100010]; int getroot(int i){ if(f[i]<0)return i;else return getroot(f[i]); } int main() { scanf("%d",&n); Rep(i,n){ scanf("%d%d%d",x+i,y+i,z+i); a[i]=make_pair(x[i],i); b[i]=make_pair(y[i],i); c[i]=make_pair(z[i],i); } sort(a,a+n); sort(b,b+n); sort(c,c+n); Rep(i,n-1)e[ne++].second=make_pair(a[i].second,a[i+1].second); Rep(i,n-1)e[ne++].second=make_pair(b[i].second,b[i+1].second); Rep(i,n-1)e[ne++].second=make_pair(c[i].second,c[i+1].second); Rep(i,ne)e[i].first=min(min(abs(x[e[i].se.fi]-x[e[i].se.se]),abs(y[e[i].se.fi]-y[e[i].se.se])),abs(z[e[i].se.fi]-z[e[i].se.se])); sort(e,e+ne); long long res=0; memset(f,-1,sizeof(f)); Rep(i,ne){ int u=getroot(e[i].se.fi); int v=getroot(e[i].se.se); if(u!=v){ res+=e[i].fi; if(f[u]<f[v])f[u]+=f[v],f[v]=u; else f[v]+=f[u],f[u]=v; } } cout<<res<<endl; return 0; }
Comments