Submission #1307906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307906		1ota	Nile (IOI24_nile)	C++20	51 / 100	89 ms	21292 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"

using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define ff first
#define ss second
#define entire(x) (x).begin(), (x).end()

using Edge = array<ll, 3>;
const ll inf = 9e18;

struct DSU{
    int n, cur;
    vector<ll> parent, odd, even, oth, sz, cost;

    DSU (int n, vector<ll> cost) : n(n), cost(cost), even(cost){
        odd.resize(n, inf); oth.resize(n, inf); sz.resize(n, 1);
        parent.resize(n); iota(entire(parent), 0);
        cur = accumulate(entire(cost), 0ll);
    }

    int pi(int u){
        return (parent[u] == u) ? u : (parent[u] = pi(parent[u]));
    }

    void merge (int u, int v){
        int pu = pi(u), pv = pi(v), delta;
        if (pu == pv){
            delta = (sz[pu] % 2) * min(oth[pu], even[pu]);
            oth[pu] = min(oth[pu], cost[u+1]); 
            delta -= (sz[pu] % 2) * min(oth[pu], even[pu]);
            cur -= delta; return;
        } if (pv < pu) swap(pu, pv);
        delta = (sz[pu] % 2) * min(oth[pu], even[pu]) + (sz[pv] % 2) * min(oth[pv], even[pv]);
        parent[pv] = pu; oth[pu] = min(oth[pu], oth[pv]);
        if (sz[pu] % 2 == 0){
            even[pu] = min(even[pu], even[pv]);
            odd[pu] = min(odd[pu], odd[pv]);
        } else {
            even[pu] = min(even[pu], odd[pv]);
            odd[pu] = min(odd[pu], even[pv]);
        } sz[pu] += sz[pv]; 
        delta -= (sz[pu] % 2) * min(oth[pu], even[pu]); cur -= delta;
    }
};

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> qn){
    int n = (ll) A.size(), q = (ll) qn.size();
    vector<pii> a(n);
    for (int i = 0; i < n; i++) a[i] = pii{W[i], A[i] - B[i]};
    sort(entire(a));

    ll base = accumulate(entire(B), 0ll);

    vector<ll> cost(n);
    for (int i = 0; i < n; i++) cost[i] = a[i].ss;
    DSU dsu(n, cost);

    vector<ll> r(q);
    vector<pii> qs(q), edge;
    for (int i = 0; i < q; i++) qs[i].ff = qn[i], qs[i].ss = i;
    sort(entire(qs));

    vector<Edge> sedge;
    for (int i = 0; i < n-1; i++){
        int idx = edge.size();
        edge.push_back(pii{i, i+1});
        sedge.push_back(Edge{a[i+1].ff - a[i].ff, 0, idx});
    }

    for (int i = 0; i < n-2; i++){
        int idx = edge.size();
        edge.push_back(pii{i, i+2});
        sedge.push_back(Edge{a[i+2].ff - a[i].ff, 1, idx});
    } sort(entire(sedge));

    int ne = sedge.size(), i = 0;
    for (auto [d, idx] : qs){
        while (i < ne and sedge[i][0] <= d){
            auto [u, v] = edge[sedge[i][2]];
            dsu.merge(u, v); i++;
        }
        r[idx] = base + dsu.cur;
    }

    return r;
}

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