CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:LiminalAlien
Submission time:2021-10-11 14:49:30 +0300
Language:C++ (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)