oj.uz

Submission #374364

# Submission time Handle Problem Language Result Execution time Memory
374364 2021-03-07T08:19:26 Z topovik Sjekira (COCI20_sjekira) C++14
0 / 110
 702 ms 524292 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]));
}

ll 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;
}

Compilation message

sjekira.cpp: In function 'll unite(ll, ll)':
sjekira.cpp:34:1: warning: no return statement in function returning non-void [-Wreturn-type]
   34 | }
      | ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 628 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 702 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 628 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 628 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -