17BUnreviewed1500GPT-5.4 (high)

Hierarchy

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Ignore the costs for a second. If you start at some employee and keep moving to their supervisor, how do the qualifications $q$ change along that path?

Because every allowed edge satisfies $q_a > q_b$ , any chosen supervisor chain is strictly increasing in $q$ when followed upward. So ask yourself: can a directed cycle even exist here?

Who can be the root? Any employee with maximum qualification has no possible supervisor, because nobody has strictly larger $q$ . So if the maximum value appears more than once, you're already screwed: you'd get at least two roots.

Suppose there is a unique employee $r$ with maximum qualification. Then every other employee just needs exactly one incoming edge from some higher-qualified employee. Since cycles are impossible anyway, the choice for one vertex does not interfere with the choice for another.

The answer is simply

\text{ans} = \sum_{v \ne r} \min_{(u\to v)} c(u,v),

where $r$ is the unique employee with maximum qualification. If there is no such unique $r$ , or some $v \ne r$ has no incoming application at all, output $-1$ . That's it — no MST black magic, no Edmonds, no DSU cosplay.

Observation 1

This problem looks like it wants some scary directed-tree algorithm. It doesn't. The qualification constraint completely neuters the hard part.

For every allowed application $u \to v$ , we know

q_u > q_v.

So if $v$ chooses $u$ as its supervisor, then moving upward in the hierarchy strictly increases qualification.

That immediately implies:

a directed cycle is impossible, because along a cycle we'd need $q_{x_1} < q_{x_2} < \cdots < q_{x_k} < q_{x_1},$ which is nonsense;
if every employee except one has exactly one supervisor, the result is automatically a rooted tree.

So the usual headache of "what if my parent choices create a cycle?" is gone. Dead. Buried.

Observation 2

Who can be the root?

Any employee with maximum qualification cannot have a supervisor at all, because there is no employee with strictly larger qualification.

Therefore:

if the maximum qualification appears more than once, then all those employees would have to be roots;
but the hierarchy must have exactly one root.

So a necessary condition is:

\text{there is exactly one employee } r \text{ with maximum } q.

And if that holds, $r$ is forced to be the root.

Observation 3

Now fix that unique root $r$ .

Every other employee $v \ne r$ must choose exactly one supervisor, i.e. exactly one incoming application $u \to v$ .

Since cycles cannot happen, the choices for different vertices are completely independent. There is no global interaction left. For each vertex $v \ne r$ , we should simply take the cheapest incoming edge.

So the optimal answer is

\text{ans} = \sum_{v \ne r} \min_{(u\to v)} c(u,v).

If some employee $v \ne r$ has no incoming application at all, then building the hierarchy is impossible.

Why does this really form one tree?

After choosing one incoming edge for every employee except $r$ :

$r$ has indegree $0$ ;
every other node has indegree $1$ .

Follow supervisor pointers upward from any node. Qualifications strictly increase, so the chain cannot continue forever and cannot cycle. It must end at a node with no supervisor. But there is only one such node: $r$ .

Hence every employee reaches $r$ , so all employees belong to the same rooted tree.

Algorithm

Find the maximum qualification.
If it occurs more than once, print $-1$ .
Let $r$ be the unique employee with maximum qualification.
For every application $a \to b$ with cost $c$ , keep $\text{best}[b] = \min(\text{best}[b], c).$
For every employee $v \ne r$ $v \neq = r$ :
- if $\text{best}[v]$ does not exist, print $-1$ ;
- otherwise add it to the answer.

Complexity

We scan the employees once and the applications once.

Time: $O(n + m)$
Memory: $O(n)$

Very cheap. Almost suspiciously cheap. But the strict qualification order is doing all the heavy lifting.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() { setIO();
    int n;
    cin >> n;

    vector<int> q(n + 1);
    int mx = -1, root = -1, cntMax = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> q[i];
        if (q[i] > mx) {
            mx = q[i];
            root = i;
            cntMax = 1;
        } else if (q[i] == mx) {
            ++cntMax;
        }
    }

    int m;
    cin >> m;

    const ll INF = (1LL << 60);
    vector<ll> best(n + 1, INF);

    for (int i = 0; i < m; ++i) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        // The statement guarantees q[a] > q[b], but checking doesn't hurt.
        if (q[a] > q[b]) best[b] = min(best[b], c);
    }

    if (cntMax != 1) {
        cout << -1 << '\n';
        return 0;
    }

    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (i == root) continue;
        if (best[i] == INF) {
            cout << -1 << '\n';
            return 0;
        }
        ans += best[i];
    }

    cout << ans << '\n';
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() { setIO();
    int n;
    cin >> n;

    vector<int> q(n + 1);
    int mx = -1, root = -1, cntMax = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> q[i];
        if (q[i] > mx) {
            mx = q[i];
            root = i;
            cntMax = 1;
        } else if (q[i] == mx) {
            ++cntMax;
        }
    }

    int m;
    cin >> m;

    const ll INF = (1LL << 60);
    vector<ll> best(n + 1, INF);

    for (int i = 0; i < m; ++i) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        // The statement guarantees q[a] > q[b], but checking doesn't hurt.
        if (q[a] > q[b]) best[b] = min(best[b], c);
    }

    if (cntMax != 1) {
        cout << -1 << '\n';
        return 0;
    }

    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (i == root) continue;
        if (best[i] == INF) {
            cout << -1 << '\n';
            return 0;
        }
        ans += best[i];
    }

    cout << ans << '\n';
}

View on Codeforces Back to the list