Task: | Tietoverkko |
Sender: | LiminalAlien |
Submission time: | 2021-10-11 14:49:30 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 10 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 10 |
#2 | TIME LIMIT EXCEEDED | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
#3 | TIME LIMIT EXCEEDED | -- | 3 | details |
Code
using namespace std;#include <iostream>#include <vector>#include <map>#define ll long longvector<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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
input |
---|
200000 1 2 613084013 1 3 832364259 2 4 411999902 3 5 989696303 ... |
correct output |
---|
1080549209850010931 |
user output |
---|
(empty) |