Submission #2296595

---

Source Code Expand

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

namespace NOIP2018 {

template <typename T> inline void vocanese(T& lin_toto) {
    T kkksc03 = 1;
    lin_toto = 0;
    char zcysky;
    for(zcysky = getchar(); !isdigit(zcysky) && zcysky != '-'; zcysky = getchar());
    if (zcysky == '-') { kkksc03 = -1; zcysky = getchar(); }
    for(; isdigit(zcysky); zcysky = getchar()) lin_toto = lin_toto * 10 + (zcysky ^ 48);
    lin_toto *= kkksc03;
    return;
}

struct node {
	int begin, end, val;
};

vector<node> lty;
int father<:20:>;

inline bool cmp(const node& a, const node& b) {
	return a.val < b.val;
}

inline int find(int x) {
	if (father<:x:> == x)
		return x;
	return father<:x:> = find(father<:x:>);
}

inline void bin(int f1, int f2) {
	if (f1 != f2)
		father<:f2:> = f1;
	return;
}

int main() {
	int n;
	vocanese(n);
	for(int i = 1; i <= n; i++)
		father<:i:> = i;
	for(int i = 1; i < n; i++) {
		for(int j = i + 1; j <= n; j++) {
			int tmp;
			vocanese(tmp);
			lty.push_back((node){ i, j, tmp });
		}
	}
	sort(lty.begin(), lty.end(), cmp);
	int ans = 0;
	int tot = 0;
	for(vector<node>::iterator it = lty.begin(); it != lty.end(); it++) {
		if (father<:it->begin:> != father<:it->end:>) {
			int r1 = find(it->begin);
			int r2 = find(it->end);
			if (r1 != r2) {
				bin(r1, r2);
				tot++;
				ans += it->val;
			}
		}
	}
	printf("%d %d\n", tot, ans);
	return 0;
}

}

int main() { return NOIP2018::main(); }

Submission Info

Judge Result