Submission #1247271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247271		Numberz	Nile (IOI24_nile)	C++20	100 / 100	129 ms	24132 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define vvll vector<vll>
#define pll pair<ll, ll>
#define pill pair<ll, pll>
#define vpll vector<pll>
const ll INF = 1e17;

struct DSU {

    ll n, totalcost = 0;
    //id = comp, size = size, evenpot = min cost of element on even position, odd same (where can )
    //
    vll id, size, anyevenopt, anyoddopt, skipeven, skipodd, cost, mn, C;
    DSU(vll& _C) {
        n = _C.size();
        for (int i = 0; i < n; i++) {
            C.push_back(_C[i]);
            id.push_back(i);
            size.push_back(1);
            anyevenopt.push_back(i&1 ? INF : _C[i]);
            anyoddopt.push_back(i&1 ? _C[i] : INF);
            skipeven.push_back(INF);
            skipodd.push_back(INF);
            cost.push_back(_C[i]);
            totalcost += _C[i];
            mn.push_back(i);
        }
    }

    ll find(int x) {return x==id[x] ? x : id[x] = find(id[x]);}

    void unite_consecutive(int a, int b) {
        //here we are joining i, i+1
        a = find(a); b = find(b);
        if (size[a] < size[b]) swap(a, b);
        //if part of same component -> ignore I guess??
        if (a==b) return;
        //now we need to join the information
        ll newsize = size[a] + size[b];
        ll newaeopt = min(anyevenopt[a], anyevenopt[b]), newaopt = min(anyoddopt[a], anyoddopt[b]);
        ll newskipeven = min(skipeven[a], skipeven[b]), newskipodd = min(skipodd[a], skipodd[b]);
        ll newmn = min(mn[a], mn[b]);
        ll newcost = INF;
        if (newsize&1) {
            //skip any same parity (even, skip, even) or skip skip other parity (odd, skip, odd) with (_,_)
            if (newmn&1) newcost = min({newcost, newaopt, newskipeven});
            else newcost = min({newcost, newaeopt, newskipodd});
        } else newcost = 0;
        //now join all info together
        totalcost = totalcost - cost[a] - cost[b] + newcost;
        id[b] = a; size[a] = newsize; anyevenopt[a] = newaeopt; anyoddopt[a] = newaopt; skipeven[a] = newskipeven; skipodd[a] = newskipodd;
        cost[a] = newcost; mn[a] = newmn;
    }

    void unite_skip(int i) {
        //i will be in a specific component a
        int a = find(i);
        //we just have to update the skip vals
        if (i&1) {
            //we update odd skip (i is already included in anyskip)
            skipodd[a] = min(skipodd[a], C[i]);
        } else skipeven[a] = min(skipeven[a], C[i]);
        if (size[a]&1) {
            //update the cost
            if ((i-mn[a])%2) {
                ll newcost = (i&1 ? min(cost[a], skipodd[a]) : min(cost[a], skipeven[a]));
                totalcost = totalcost - cost[a] + newcost;
                cost[a] = newcost;
            }
        }
    }

};


vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {

    reverse(A.begin(), A.end()); reverse(W.begin(), W.end()); reverse(B.begin(), B.end());

    int n = A.size(), q = E.size();
    vll C(n, 0), res(q, 0);
    ll basecost = accumulate(B.begin(), B.end(), 0LL);
    for (int i = 0; i < n; i++) C[i] = A[i] - B[i];
    priority_queue<pill, vector<pill>, greater<pill>> events;

    //here all indicies are sorted by Weight
    vll indices(n);
    iota(indices.begin(), indices.end(), 0);
    sort(indices.begin(), indices.end(), [&](int i, int j) {return W[i] < W[j];});

    for (int i = 0; i < n-1; i++) events.push({abs(W[indices[i]] - W[indices[i+1]]), {0, i}});
    for (int i = 1; i < n-1; i++) events.push({abs(W[indices[i+1]] - W[indices[i-1]]), {1, i}});
    for (int i = 0; i < q; i++) events.push({E[i], {2, i}});
    vll _C;
    for (int i : indices) _C.push_back(C[i]);
    DSU uf(_C);

    while (!events.empty()) {

        auto p = events.top();
        events.pop();
        if (p.second.first==2) {
            //process query;
            res[p.second.second] = uf.totalcost+basecost;
        } else if (p.second.first==0) {
            //joining two consecutive things
            int a = p.second.second, b = p.second.second+1;
            uf.unite_consecutive(a, b);
        } else {
            //joining 2 seperate
            int i = p.second.second;
            uf.unite_skip(i);
        }

    }
    return res;
    
}

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