# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
807343 | Tunglam07 | Odašiljači (COCI20_odasiljaci) | C++17 | 1 ms | 468 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
long long n, a[100001], parent[100001], ans[100001], sum = 0;
pair<int, pair<int, int>> connect[100001];
int findparent(int id)
{
if(id == parent[id])
{
return id;
}
else
{
return parent[id] = findparent(parent[id]);
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; ++i)
{
cin >> a[i];
parent[i] = i;
ans[i] = a[i];
}
for(int i = 1; i < n; ++i)
{
cin >> connect[i].second.first >> connect[i].second.second;
connect[i].first = max(a[connect[i].second.first], a[connect[i].second.second]);
}
sort(connect + 1, connect + n);
for(int i = 1; i < n; ++i)
{
long long x = findparent(connect[i].second.first), y = findparent(connect[i].second.second);
sum = sum + ans[x] + ans[y];
if(x != y)
{
parent[x] = y;
ans[y] = max(ans[x], ans[y]);
}
}
cout << sum;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |