CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:LiminalAlien
Submission time:2021-10-11 14:49:30 +0300
Language:C++11
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2--2, 3details
#3--3details

Code

using namespace std;
#include <iostream>
#include <vector>
#include <map>

#define ll long long

vector<pair<ll,ll>> c[200001];
pair<ll,ll> p[200001];
ll d[200001];
map<pair<ll, ll>, ll> m;

void haku(ll n, ll k, ll s)
{
	if (n != k)
	{
		m[{n, k}] = s;
		d[k]++; d[n]++;
	}
	for (auto i : c[k])
	{
		if (i.second < s)haku(n, i.first, i.second);
		else haku(n, i.first, s);
	}
}

int main()
{
	ll n;
	cin >> n;
	for (ll i = 1; i < n; i++)
	{
		ll a, b, x;
		cin >> a >> b >> x;
		c[a].push_back({ b,x });
		p[b] = { a,x };
	}
	for (ll i = 1; i <= n; i++)
		haku(i, i, 1e9);
	for (ll i = 1; i <= n; i++)
	{
		if (d[i] != n-1)
		{
			for (ll j = 1; j <= n; j++)
			{
				if (j != i && !m.count({ i,j }) && !m.count({ j,i }))
				{
					if (p[i].second < m[{p[i].first, j}])m[{i, j}] = p[i].second;
					else m[{i, j}] = m[{p[i].first, j}];
					d[i]++; d[j]++;
				}
			}
		}
	}
	ll ans = 0;
	for (auto i : m)
		ans += i.second;
	cout << ans;
}

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:

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

correct output
1103702320243776

user output
(empty)

Test 3

Group: 3

Verdict:

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

correct output
1080549209850010931

user output
(empty)