CCC '10 S4 - Animal Farm

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#define f first
#define s second
#define mp(a, b) make_pair(a, b)

using namespace std;

struct s{
    int pr;
    int rnk;
};

int f(int a, struct s ss[]){
    if(ss[a].pr == a) return a;
    else return ss[a].pr = f(ss[a].pr, ss);
}

void un(int a, int b, struct s ss[]){
    if(ss[a].rnk > ss[b].rnk){
        ss[b].pr = ss[a].pr;
        ss[a].rnk++;
    }else{
        ss[a].pr = ss[b].pr;
        ss[b].rnk++;
    }
}

int main()
{
    int m, e;
    int i, j, k, l;
    scanf(" %d", &m);
    int a, b;
    int y;
    int c;
    int sum1, sum2;
    sum1 = sum2 = 0;

    pair<int, pair<int, int> > p;

    struct s ss[m+1];
    for(i=0; i<=m; i++){
        ss[i].pr = i;
        ss[i].rnk = 0;
    }

    vector <pair<pair<int, int>, int> > edg[m]; //indices, weight
    vector <pair<pair<int, int>, int> >:: iterator pos; //indices, weight
    vector <pair<int, int> > cnnct[m+1]; //weight, index

    priority_queue <pair<int, pair<int, int>>, vector< pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > q; //weight, connections w/o outside
    priority_queue <pair<int, pair<int, int>>, vector< pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > q2;//w/ outside

    for(i=0; i<m; i++){
        scanf(" %d", &e);
        int ar[e][3];

        for(j=0; j<e; j++){
            scanf(" %d", &a);

            edg[i].push_back(mp(mp(a, 0), 0));

            if(j>0){
                edg[i][j-1].f.s = edg[i][j].f.f;
            }

            if(j == e-1){
                edg[i][j].f.s = edg[i][0].f.f;
            }
        }

        for(j=0; j<e; j++){
            scanf(" %d", &a);
            edg[i][j].s = a;
            if(edg[i][j].f.f  > edg[i][j].f.s){
                a = edg[i][j].f.s; //a used as temp
                edg[i][j].f.s = edg[i][j].f.f;
                edg[i][j].f.f = a;
            }
        }
    }

    for(i=0; i<m; i++){ 
        for(j=0; j<edg[i].size(); j++){
            y = 0;
            for(k=i+1; k<m; k++){
                pos = find(edg[k].begin(), edg[k].end(), edg[i][j]);
                if(pos != edg[k].end()){
                    cnnct[i].push_back(mp(edg[i][j].s, k));
                    cnnct[k].push_back(mp(edg[i][j].s, i));
                    q.push(mp(edg[i][j].s, mp(i, m)));
                    q2.push(mp(edg[i][j].s, mp(i, k)));
                    edg[k].erase(pos);
                    y = 1;
                    break;
                }
            }

            if(!y){ 
                cnnct[i].push_back(mp(edg[i][j].s, m));
                cnnct[m].push_back(mp(edg[i][j].s, i));
                q2.push(mp(edg[i][j].s, mp(i, m)));
            }
        }
    }
    c = 0;
    while(!q.empty()){ //two mst w/ and w/o outside
        p = q.top();
        q.pop();


        a = f(p.s.f, ss);
        b = f(p.s.s, ss);

        if(a != b){
            c++;
            sum1 += p.f;
            un(a, b, ss);
        }
    }

    if(c != m-1) sum1 = 1000000000;
    c = 0;

    for(i=0; i<=m; i++){
        ss[i].pr = i;
        ss[i].rnk = 0;
    }

    while(!q2.empty()){
        p = q2.top();
        q2.pop();

        a = f(p.s.f, ss);
        b = f(p.s.s, ss);

        if(a != b){
            c++;
            sum2 += p.f;
            un(a, b, ss);
        }
    }

    if(c != m) sum2 = 1000000000;

    printf("%d", min(sum1, sum2));

    return 0;
}