CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:intoo
Submission time:2021-10-04 22:45:31
Language:C++17
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#3ACCEPTED75
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s2, 3details
#3ACCEPTED0.23 s3details

Code

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;
using ll = long long;

ll k[200200], s[200200];
vector<tuple<int, int, int>> q;

int id(int x);
bool same(int a, int b);
void join(int a, int b);

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		k[i] = i;
		s[i] = 1;
	}
	for (int i = 1; i < n; ++i) {
		int a, b, x;
		cin >> a >> b >> x;
		q.emplace_back(x, a, b);
	}
	sort(q.begin(), q.end(), greater<tuple<int, int, int>>());
	ll t = 0;
	for (auto [x, a, b] : q) {
		if (same(a, b)) {
			t += x;
		} else {
			t += s[id(a)]*s[id(b)]*x;
			join(a, b);
		}
	}
	cout << t << endl;
}

int id(int x)
{
	while (k[x] != x)
		x = k[x];
	return x;
}

bool same(int a, int b)
{
	return id(a) == id(b);
}

void join(int a, int b)
{
	a = id(a);
	b = id(b);
	if (s[a] < s[b]) swap(a, b);
	k[b] = a;
	s[a] += s[b];
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
88687

Test 2

Group: 2, 3

Verdict: ACCEPTED

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
1103702320243776

Test 3

Group: 3

Verdict: ACCEPTED

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
1080549209850010931