Submission #1099752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099752		model_code	Nile (IOI24_nile)	C++17	100 / 100	73 ms	8228 KiB

nile

// correct/arshia_solution.cpp

#include "nile.h"
#include <tuple>
#include <vector>
#include <numeric>
#include <climits>
#include <algorithm>
#include <cassert>
using namespace std;

struct DSU {
    vector<int> parent, size;
    vector<int> even, odd;
    long long cost = 0;

    DSU(vector<int> &A, vector<int> &B) : parent(A.size(), -1), size(A.size(), 1), even(A.size()), odd(A.size(), INT_MAX) {
        for (int i = 0; i < A.size(); i++) {
            even[i] = A[i] - B[i];
            cost += even[i];
        }
    }
    int get_par(int x) {
        return ~parent[x] ? parent[x] = get_par(parent[x]) : x;
    }
    void merge(int v) {
        int u = get_par(v - 1);
        for (int x : {u, v})
            if (size[x] & 1)
                cost -= even[x];

        if (size[u] & 1)
            swap(even[v], odd[v]);
        odd[u] = min(odd[u], odd[v]);
        even[u] = min(even[u], even[v]);

        parent[v] = u;
        size[u] += size[v];
        if (size[u] & 1)
            cost += even[u];
    }
    void consider(int v, int w) {
        int u = get_par(v);
        if (v - u & 1) {
            if (size[u] & 1)
                cost -= even[u];
            even[u] = min(even[u], w);
            if (size[u] & 1)
                cost += even[u];
        }
        else
            odd[u] = min(odd[u], w);
    }
};

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int n = W.size(), q = E.size();
    if (n == 1)
        return vector<long long>(q, A[0]);

    vector<tuple<int, int, int>> helper;
    for (int i = 0; i < n; i++)
        helper.push_back({W[i], A[i], B[i]});
    sort(helper.begin(), helper.end());
    for (int i = 0; i < n; i++)
        tie(W[i], A[i], B[i]) = helper[i];

    vector<int> diff1(n - 1);
    iota(diff1.begin(), diff1.end(), 1);
    sort(diff1.begin(), diff1.end(), [&](int i, int j) {
        return W[i] - W[i - 1] < W[j] - W[j - 1];
    });

    vector<int> diff2(n - 2);
    iota(diff2.begin(), diff2.end(), 1);
    sort(diff2.begin(), diff2.end(), [&](int i, int j) {
        return W[i + 1] - W[i - 1] < W[j + 1] - W[j - 1];
    });

    vector<int> indexes(q);
    iota(indexes.begin(), indexes.end(), 0);
    sort(indexes.begin(), indexes.end(), [&](int i, int j) {
        return E[i] < E[j];
    });

    DSU dsu(A, B);
    int p1 = 0, p2 = 0;
    vector<long long> costs(q);
    long long total = accumulate(B.begin(), B.end(), 0LL);
    for (int index : indexes) {
        while (p1 < n - 1 && W[diff1[p1]] - W[diff1[p1] - 1] <= E[index]) {
            int idx = diff1[p1++];
            dsu.merge(idx);

            for (int p : {idx, idx - 1})
                if (p && p < n - 1 && W[p + 1] - W[p - 1] <= E[index] && dsu.get_par(p + 1) == dsu.get_par(p - 1))
                    dsu.consider(p, A[p] - B[p]);
        }
        while (p2 < n - 2 && W[diff2[p2] + 1] - W[diff2[p2] - 1] <= E[index]) {
            int idx = diff2[p2++];
            if (dsu.get_par(idx + 1) == dsu.get_par(idx - 1))
                dsu.consider(idx, A[idx] - B[idx]);
        }
        costs[index] = total + dsu.cost;
    }

    return costs;
}

Compilation message (stderr)

nile.cpp: In constructor 'DSU::DSU(std::vector<int>&, std::vector<int>&)':
nile.cpp:18:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for (int i = 0; i < A.size(); i++) {
      |                         ~~^~~~~~~~~~
nile.cpp: In member function 'void DSU::consider(int, int)':
nile.cpp:44:15: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   44 |         if (v - u & 1) {
      |             ~~^~~

• 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