[ create a new paste ] login | about

Link: http://codepad.org/kcA7N9Z9    [ raw code | output | fork ]

C++, pasted on Apr 1:
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int,int> pi;
 
struct disj{
    int pa[100005], r[100005];
    void init(int n){
        for (int i=1; i<=n; i++) pa[i] = i, r[i] = 0;
        //memset(r,0,sizeof(r));
        pa[0] = 0;
    }
    int find(int x){
        if(pa[x] == x) return x;
        return pa[x] = find(pa[x]);
    }
    bool uni(int p, int q){
        p = find(p);
        q = find(q);
        if(p == q) return 0;
        if(r[p] < r[q]) pa[q] = p;
        else pa[p] = q;
        if(r[p] == r[q]) r[p]++;
        return 1;
    }
}disj;
 
struct edg{int x,s,e;}a[300005];
bool cmp(edg a, edg b){return a.x < b.x;}
 
vector<pi> lx, ly, lz;
 
int n;
 
int main(){
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        lx.push_back(pi(x,i+1));
        ly.push_back(pi(y,i+1));
        lz.push_back(pi(z,i+1));
    }
    sort(lx.begin(),lx.end());
    sort(ly.begin(),ly.end());
    sort(lz.begin(),lz.end());
    for (int i=0; i<n-1; i++) {
        a[3*i] = (edg){lx[i+1].first - lx[i].first,lx[i].second,lx[i+1].second};
        a[3*i+1] = (edg){ly[i+1].first - ly[i].first,ly[i].second,ly[i+1].second};
        a[3*i+2] = (edg){lz[i+1].first - lz[i].first,lz[i].second,lz[i+1].second};
    }
    long long ret = 0;
    sort(a,a+3*n-3,cmp);
    disj.init(n);
    for (int i=0; i<3*n-3; i++) {
        if(disj.uni(a[i].s,a[i].e)){
            ret += a[i].x;
        }
    }
    printf("%lld\n",ret);
}


Output:
1
2
3
In function 'int main()':
Line 50: error: ISO C++ forbids compound-literals
compilation terminated due to -Wfatal-errors.


Create a new paste based on this one


Comments: