HackerRank: World codesprint #4 - Roads in HackerLand - C++ code study III

RoadsInHackerLand4B.cpp

#include <bits/stdc++.h>
using namespace std;

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
void PR(vi &v) { trav(x, v) cout << x << ' '; cout << endl; }

struct UF {
	vi v;
	UF(int n) : v(n, -1) {}
	int find(int x) {
		return v[x] < 0 ? x : v[x] = find(v[x]);
	}
	void join(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return;
		if (-v[a] < -v[b]) swap(a, b);
		v[a] += v[b];
		v[b] = a;
	}
};

vector<ll> outs;
int N;
int rec(vector<vector<pii>>& ed, int at, int par) {
	int s = 1;
	trav(x, ed[at]) {
		if (x.first == par) continue;
		int s2 = rec(ed, x.first, at);
		outs[x.second] = s2 * (ll)(N - s2);
		s += s2;
	}
	return s;
}

int main() {
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	int M;
	cin >> N >> M;
	outs.resize(M+100);
	UF uf(N);
	vector<tuple<int,int,int>> eds;
	rep(i,0,M) {
		int a, b, c;
		cin >> a >> b >> c;
		--a, --b;
		eds.emplace_back(c, a, b);
	}
	sort(all(eds));
	vector<vector<pii>> ed(N);
	trav(pa, eds) {
		int a,b,c;
		tie(c,a,b) = pa;
		if (uf.find(a) == uf.find(b)) continue;
		uf.join(a,b);
		ed[a].emplace_back(b, c);
		ed[b].emplace_back(a, c);
	}
	int s = rec(ed, 0, -1);
	assert(s == N);

	ll carry = 0;
	string res;
	rep(i,0,M+100) {
		carry += outs[i];
		res += (char)('0' + (carry & 1));
		carry >>= 1;
	}
	while (res.size() > 1 && res.back() == '0') res.pop_back();
	reverse(all(res));
	cout << res << endl;
}