Submission #1186200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186200		raspy	Nile (IOI24_nile)	C++20	38 / 100	58 ms	11196 KiB

nile

#include "nile.h"
#include <algorithm>
#include <numeric>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

ll findp(vector<ll>& par, ll x) {
    return par[x] == x ? x : par[x] = findp(par, par[x]);
}

vector<long long> calculate_costs(vector<int> w, vector<int> A, vector<int> B, vector<int> E) {
    ll n = A.size();
    ll q = E.size();
    vector<ll> par(n);
    vector<ll> sz(n, 1);
    vector<ll> mn(n), sm(n);

    for (ll i = 0; i < n; i++) {
        par[i] = i;
        sm[i] = (ll)A[i] - B[i];  // saving for artifact i.
        mn[i] = sm[i];            // for a singleton, the min saving equals its saving.
    }
    ll tre = 0;
    for (ll i = 0; i < n; i++) {
        tre += A[i];
    }

    vector<ll> ixsw(n);
    iota(ixsw.begin(), ixsw.end(), 0);
    sort(ixsw.begin(), ixsw.end(), [&w](ll i, ll j) {
        return w[i] < w[j];
    });

    vector<pair<ll,ll>> queries(q);
    for (ll i = 0; i < q; i++) {
        queries[i] = { E[i], i };
    }
    sort(queries.begin(), queries.end());

    vector<pair<ll,ll>> edges;
    for (ll i = 0; i + 1 < n; i++) {
        edges.push_back({ ixsw[i], ixsw[i+1] });
    }
    sort(edges.begin(), edges.end(), [&w](pair<ll,ll> p1, pair<ll,ll> p2) {
        return abs(w[p1.first] - w[p1.second]) < abs(w[p2.first] - w[p2.second]);
    });

    vector<ll> rez(q);
    ll edgeIndex = 0;

    for (ll i = 0; i < q; i++) {
        ll d = queries[i].first;
        ll qIdx = queries[i].second;
        while (edgeIndex < edges.size() &&
               abs(w[edges[edgeIndex].first] - w[edges[edgeIndex].second]) <= d) {
            ll u = edges[edgeIndex].first;
            ll v = edges[edgeIndex].second;
            ll ru = findp(par, u);
            ll rv = findp(par, v);
            if (ru == rv) {
                edgeIndex++;
                continue;
            }
            ll disc_ru = (sz[ru] % 2 == 1) ? (sm[ru] - mn[ru]) : sm[ru];
            ll disc_rv = (sz[rv] % 2 == 1) ? (sm[rv] - mn[rv]) : sm[rv];
            ll oldDiscount = disc_ru + disc_rv;
            if (sz[ru] < sz[rv]) {
                swap(ru, rv);
            }
            par[rv] = ru;
            sz[ru] += sz[rv];
            sm[ru] += sm[rv];
            mn[ru] = min(mn[ru], mn[rv]);
            ll newDiscount = (sz[ru] % 2 == 1) ? (sm[ru] - mn[ru]) : sm[ru];
            tre -= (newDiscount - oldDiscount);

            edgeIndex++;
        }
        rez[qIdx] = tre;
    }
    return rez;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18