Submission #77528

---

Source Code Expand

#include <vector>
#include <algorithm>
#include "grader.h"

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define fi first
#define se second
#define mp make_pair
#define pb push_back

typedef pair<int, int> P;
typedef long long ll;

vector<P> g[100010];

struct unionfind{
    int par[100010], rank[100010];

    void init(){
	rep(i, 100000){
	    par[i] = i;
	    rank[i] = 0;
	}
    }

    inline int find(int x){
	if(par[x] == x) return x;
	return par[x] = find(par[x]);
    }

    inline void unite(int x, int y){
	x = find(x), y = find(y);
	if(x == y) return ;
	if(rank[x] < rank[y]) par[x] = y;
	else {
	    par[y] = x;
	    rank[x] += (rank[x] == rank[y]);
	}
    }

    inline bool same(int a, int b){ return find(a) == find(b); }
}uf;

struct edge{
    int f, t, c;
    edge(int f, int t, int c) : f(f), t(t), c(c){}
    edge(){}
};

bool cmp(edge a, edge b){
    return a.c < b.c;
}

vector<edge> eg;

void construct(int n, int m, int e[][3]){
    rep(i, m) g[e[i][1]].pb(mp(e[i][0], e[i][2]));
    rep(i, n - 1){
	int v = i + 1;
	rep(j, g[v].size()){
	    eg.pb(edge(i, g[v][i].fi, g[v][i].se));
	}
	sort(eg.begin(), eg.end());
	uf.init();
	int sz = v + 1;
	ll ans = 0;
	rep(j, eg.size()){
	    edge crt = eg[j];
	    if(uf.same(crt.f, crt.t)) continue;
	    uf.unite(crt.f, crt.t);
	    --sz;
	    ans += crt.c;
	}
	if(sz != 0){
	    answer(-1);
	}else{
	    answer(ans);
	}
    }
}

Submission Info

Compile Error

In file included from /usr/include/c++/4.4/algorithm:62,
                 from ./Main.cpp:2:
/usr/include/c++/4.4/bits/stl_algo.h: In function ‘const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&) [with _Tp = edge]’:
/usr/include/c++/4.4/bits/stl_algo.h:2268:   instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge, std::allocator<edge> > >, _Size = long int]’
/usr/include/c++/4.4/bits/stl_algo.h:5220:   instantiated from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<edge*, std::vector<edge, std::allocator<edge> > >]’
./Main.cpp:65:   instantiated from here
/usr/include/c++/4.4/bits/stl_algo.h:89: error: no match for ‘operator<’ in ‘__a < __b’
/usr/include/c++/4.4/bits/stl_algo.h:90: error: no match for ‘operator<’ in ‘__b < __c’
/usr/include/c++/4.4/bits/stl_algo.h:92: error: no match for ‘operator<’ in ‘__a <...