제출 #1317373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317373		spetr	나일강 (IOI24_nile)	C++20	51 / 100	63 ms	12068 KiB

nile

#include <vector>
#include <algorithm>
#include <numeric>
#include <iostream>

using namespace std;

typedef long long ll;

struct Artifact {
    int id;
    int w;
    ll diff; // Cena navíc za to, že je sám (A - B)
};

struct Event {
    int w;     // Váha hrany nebo dotazu
    int type;  // 1: Hrana (i, i+1), 2: Hrana (i, i+2), 3: Dotaz
    int idx;   // Index
    
    // Řazení: Podle váhy. Při shodě vah mají přednost hrany před dotazy (Type 1/2 < Type 3)
    bool operator<(const Event& other) const {
        if (w != other.w) return w < other.w;
        return type < other.type;
    }
};

struct DSU {
    vector<int> parent;
    vector<int> sz;           // Velikost komponenty
    vector<ll> min_diff[2];   // min_diff[0]: min(A-B) pro sudé indexy, [1] pro liché
    vector<int> min_idx;      // Nejnižší index v komponentě (určuje paritu majority)
    vector<bool> can_swap;    // Máme hranu typu 2 (skok)?
    
    ll current_penalty = 0;   // Součet penalizací všech LICHÝCH komponent

    DSU(int n, const vector<Artifact>& arts) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        sz.assign(n, 1);
        min_diff[0].assign(n, 2e18); // Inicializace "nekonečnem"
        min_diff[1].assign(n, 2e18);
        min_idx.resize(n);
        can_swap.assign(n, false);

        for(int i=0; i<n; ++i) {
            min_diff[i%2][i] = arts[i].diff;
            min_idx[i] = i;
            // Na začátku je každý sám -> lichá komponenta -> platí diff
            current_penalty += arts[i].diff;
        }
    }

    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }

    // Vypočítá penalizaci pro jednu konkrétní komponentu
    ll get_penalty(int root) {
        if (sz[root] % 2 == 0) return 0; // Sudá velikost = 0 penále

        // Lichá velikost:
        // Komponenta je vždy souvislý interval [L, R] (díky vlastnosti Type 1 hran).
        // Majoritní parita (ta, které je o 1 víc) je parita L (min_idx).
        int major_parity = min_idx[root] % 2;
        
        ll val = min_diff[major_parity][root]; // Musíme obětovat někoho z majority
        
        if (can_swap[root]) {
            // Pokud máme skok, můžeme obětovat někoho z minority, pokud je to levnější
            val = min(val, min_diff[1 - major_parity][root]);
        }
        return val;
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);

        if (root_i != root_j) {
            // OPTIMALIZACE: Union by Size (připojujeme menší k většímu)
            if (sz[root_i] < sz[root_j]) swap(root_i, root_j);

            // Odečteme staré penalizace
            current_penalty -= get_penalty(root_i);
            current_penalty -= get_penalty(root_j);

            // Sloučení (j do i)
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
            
            // Aktualizace vlastností kořene
            min_diff[0][root_i] = min(min_diff[0][root_i], min_diff[0][root_j]);
            min_diff[1][root_i] = min(min_diff[1][root_i], min_diff[1][root_j]);
            min_idx[root_i] = min(min_idx[root_i], min_idx[root_j]);
            can_swap[root_i] = can_swap[root_i] | can_swap[root_j];

            // Přičteme novou penalizaci spojené komponenty
            current_penalty += get_penalty(root_i);
        }
    }

    void activate_swap(int i) {
        int root = find(i);
        if (!can_swap[root]) {
            current_penalty -= get_penalty(root);
            can_swap[root] = true;
            current_penalty += get_penalty(root);
        }
    }
};

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

    int n = W.size();
    vector<Artifact> arts(n);
    ll base_B_sum = 0; // Základní cena, kdybychom všechno spárovali (suma B)

    for(int i=0; i<n; ++i) {
        arts[i] = {i, W[i], (ll)A[i] - B[i]};
        base_B_sum += B[i];
    }
    
    // Seřadíme artefakty podle váhy
    sort(arts.begin(), arts.end(), [](const Artifact& a, const Artifact& b){
        return a.w < b.w;
    });

    vector<Event> events;
    events.reserve(2 * n + E.size()); // Prealokace pro rychlost

    // Hrany Type 1: (i, i+1)
    for(int i=0; i < n-1; ++i) {
        events.push_back({arts[i+1].w - arts[i].w, 1, i});
    }
    // Hrany Type 2: (i, i+2) - Skoky
    for(int i=0; i < n-2; ++i) {
        events.push_back({arts[i+2].w - arts[i].w, 2, i});
    }
    // Dotazy
    for(int i=0; i < E.size(); ++i) {
        events.push_back({E[i], 3, i});
    }

    sort(events.begin(), events.end());

    DSU dsu(n, arts);
    vector<ll> results(E.size());

    for(const auto& ev : events) {
        if (ev.type == 1) {
            dsu.unite(ev.idx, ev.idx+1);
        } else if (ev.type == 2) {
            dsu.activate_swap(ev.idx);
        } else {
            // Výsledek = Suma B + penalizace za liché prvky
            results[ev.idx] = base_B_sum + dsu.current_penalty;
        }
    }

    return results;
}

• 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