oj.uz

Submission #374365

# Submission time Handle Problem Language Result Execution time Memory
374365 2021-03-07T08:20:10 Z topovik Sjekira (COCI20_sjekira) C++14
40 / 110
 1000 ms 4448 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const ll N = 1e6 + 100;
const ll oo = 1e10;

ll a[N];
ll pred[N];
ll r[N];

ll cmp(ll x)
{
    if (x == pred[x]) return x;
    else return (pred[x] = cmp(pred[x]));
}

void unite(ll x, ll y)
{
    if (r[x] > r[y]) pred[y] = x;
    else
    {
        pred[x] = y;
        r[y] += (r[x] == r[y]);
    }
    a[y] = max(a[y], a[x]);
    a[x] = max(a[x], a[y]);
}

int main()
{
    ll n;
    cin >> n;
    for (ll i = 0; i < n; i++) cin >> a[i];
    for (ll i = 0; i < n; i++) pred[i] = i, r[i] = 0;
    vector <pair<ll, ll> > rebra;
    for (ll i = 0; i < n - 1; i++)
    {
        ll x, y;
        cin >> x >> y;
        rebra.pb({--x, --y});
    }
    bool mrk[n - 1];
    for (ll i = 0; i < n - 1; i++) mrk[i] = 0;
    ll ans = 0;
    for (ll i = 0; i < n - 1; i++)
    {
        ll mx1 = oo, nom = -1;
        for (ll j = 0; j < n - 1; j++)
            if (!mrk[j])
        {
            ll x = rebra[j].f, y = rebra[j].s;
            if (a[cmp(x)] + a[cmp(y)] < mx1) mx1 = a[cmp(x)] + a[cmp(y)], nom = j;
        }
        ans += mx1;
        mrk[nom] = 1;
        unite(cmp(rebra[nom].f), cmp(rebra[nom].s));
    }
    cout << ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 4448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 5 ms 364 KB Output is correct
7 Correct 4 ms 364 KB Output is correct
8 Correct 3 ms 364 KB Output is correct
9 Correct 5 ms 364 KB Output is correct
10 Correct 6 ms 364 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Execution timed out 1073 ms 4448 KB Time limit exceeded
7 Halted 0 ms 0 KB -