Submission #1208927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208927		sula2	Nile (IOI24_nile)	C++20	82 / 100	2092 ms	8636 KiB

nile

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define popcount(x) __builtin_popcountll(x)
using namespace std;
using namespace chrono;

struct dsu {
    vector<int> par, rank, size;
    int odd_comps = 0;

    dsu(int n): par(n), rank(n), size(n, 1), odd_comps(n) {
        iota(all(par), 0);
    }

    int find(int u) {
        return par[u] == u ? u : par[u] = find(par[u]);
    }

    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u != v) {
            if (rank[u] < rank[v]) swap(u, v);
            par[v] = u;
            rank[u] += rank[u] == rank[v];
            odd_comps -= size[u] & 1;
            odd_comps -= size[v] & 1;
            size[u] += size[v];
            odd_comps += size[u] & 1;
        }
    }
};

vector<long long> sub6(
        vector<int> W, vector<int> A,
        vector<int> B, vector<int> E
) {
    int n = W.size(), q = E.size();
    vector<int> E_ind(q);
    iota(all(E_ind), 0);
    sort(all(E_ind), [&](int i, int j) { return E[i] < E[j]; });
    vector<int> W_ind(n);
    iota(all(W_ind), 0);
    sort(all(W_ind), [&](int i, int j) { return W[i] < W[j]; });
    vector<pair<int,int>> edges;
    for (int i = 0; i < n-1; i++)
        edges.emplace_back(W[W_ind[i+1]] - W[W_ind[i]], i);
    sort(all(edges));
    int ptr = 0;
    dsu d(n);
    vector<long long> ans(q);
    for (int i : E_ind) {
        while (ptr < edges.size() && edges[ptr].first <= E[i]) {
            d.merge(edges[ptr].second, edges[ptr].second + 1);
            ptr++;
        }
        ans[i] = n + d.odd_comps;
    }
    return ans;
}

long long solve(vector<int> W, vector<int> A,
                vector<int> B, int D) {
    int n = W.size();
    vector<int> ind(n);
    iota(all(ind), 0);
    sort(all(ind), [&](int i, int j) { return W[i] < W[j]; });
    vector<long long> dp(n);
    dp[0] = A[ind[0]];
    for (int i = 1; i < n; i++) {
        dp[i] = dp[i-1] + A[ind[i]];
        long long sum = 0;
        for (int j = i-1; j >= 0 && W[ind[i]] - W[ind[j]] <= D && i-j <= 2; j--) {
            dp[i] = min(dp[i], (j == 0 ? 0 : dp[j-1]) + B[ind[j]] + B[ind[i]] + sum);
            sum += A[ind[j]];
        }
    }
    return dp[n-1];
}

vector<long long> calculate_costs(
        vector<int> W, vector<int> A,
        vector<int> B, vector<int> E
) {
    bool subtask6 = true;
    for (int x : A) subtask6 &= x == 2;
    for (int x : B) subtask6 &= x == 1;
    if (subtask6) {
        return sub6(W, A, B, E);
    }
    int n = W.size(), q = E.size();
    vector<long long> res(q);
    for (int i = 0; i < q; i++) {
        res[i] = solve(W, A, B, E[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: 0 / 18