Submission #1239386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239386		orcslop	Zamjene (COCI16_zamjene)	C++20	112 / 140	6096 ms	233756 KiB

zamjene

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

using namespace std;

// DSU structure to manage components (clouds)
struct DSU {
    vector<int> parent;
    vector<long long> sz;
    DSU(int n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
        sz.assign(n + 1, 1);
    }

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

// Use two hash functions to minimize collisions
const long long M1 = 1e9 + 7, P1 = 313;
const long long M2 = 1e9 + 9, P2 = 331;
const long long PAIR_P1 = 31;
const long long PAIR_P2 = 37;

// Function to compute a hash for a diff map
pair<long long, long long> get_hash(const map<int, int>& m) {
    if (m.empty()) {
        return {0, 0};
    }
    long long h1 = 0, h2 = 0;
    for (auto const& [val, count] : m) {
        long long pair_hash_1 = (val * PAIR_P1 + count) % M1;
        if (pair_hash_1 < 0) pair_hash_1 += M1;
        long long pair_hash_2 = (val * PAIR_P2 + count) % M2;
        if (pair_hash_2 < 0) pair_hash_2 += M2;
        h1 = (h1 * P1 + pair_hash_1) % M1;
        h2 = (h2 * P2 + pair_hash_2) % M2;
    }
    return {h1, h2};
}

// Function to calculate the hash of the complementary diff map
pair<long long, long long> get_complement_hash(const map<int, int>& m) {
    map<int, int> complement;
    for (auto const& [val, count] : m) {
        complement[val] = -count;
    }
    return get_hash(complement);
}

// Global state variables
DSU dsu(0);
vector<int> p;
vector<map<int, int>> diffs;
vector<pair<long long, long long>> component_hashes;
int bad_components_count = 0;
long long total_q4_pairs = 0;
map<pair<long long, long long>, long long> hash_to_total_size;

// Helper to update total pairs when a group's size changes
void update_pairs(pair<long long, long long> hash, pair<long long, long long> comp_hash, long long old_size, long long new_size){
    if (hash == make_pair(0LL, 0LL)) return;
    
    long long old_size_comp = hash_to_total_size[comp_hash];
    if (hash == comp_hash) {
         old_size_comp = old_size;
    }
    
    // Remove old contribution
    if(hash != comp_hash) {
        total_q4_pairs -= old_size * old_size_comp;
    } else {
        total_q4_pairs -= old_size * (old_size - 1) / 2;
    }

    // Add new contribution
    long long new_size_comp = hash_to_total_size[comp_hash];
     if (hash == comp_hash) {
         new_size_comp = new_size;
    }

    if(hash != comp_hash) {
        total_q4_pairs += new_size * new_size_comp;
    } else {
        total_q4_pairs += new_size * (new_size - 1) / 2;
    }
}


// Modifies a component's diff map and updates all global states
void modify_component_diff(int root, int val, int count_delta) {
    long long size = dsu.sz[root];
    pair<long long, long long> old_hash = component_hashes[root];

    // Remove old state's contribution
    if(!diffs[root].empty()){
        pair<long long, long long> old_comp_hash = get_complement_hash(diffs[root]);
        update_pairs(old_hash, old_comp_hash, hash_to_total_size[old_hash], hash_to_total_size[old_hash] - size);
        if(old_hash != old_comp_hash)
            update_pairs(old_comp_hash, old_hash, hash_to_total_size[old_comp_hash], hash_to_total_size[old_comp_hash]);
        hash_to_total_size[old_hash] -= size;
        bad_components_count--;
    }
    
    diffs[root][val] += count_delta;
    if (diffs[root][val] == 0) {
        diffs[root].erase(val);
    }
    
    pair<long long, long long> new_hash = get_hash(diffs[root]);
    component_hashes[root] = new_hash;
    
    // Add new state's contribution
    if(!diffs[root].empty()){
        pair<long long, long long> new_comp_hash = get_complement_hash(diffs[root]);
        hash_to_total_size[new_hash] += size;
        update_pairs(new_hash, new_comp_hash, hash_to_total_size[new_hash] - size, hash_to_total_size[new_hash]);
        if(new_hash != new_comp_hash)
            update_pairs(new_comp_hash, new_hash, hash_to_total_size[new_comp_hash], hash_to_total_size[new_comp_hash]);
        bad_components_count++;
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    p.resize(n + 1);
    vector<int> q_array(n + 1);
    dsu = DSU(n);
    diffs.resize(n + 1);
    component_hashes.resize(n + 1, {0, 0});

    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
        q_array[i] = p[i];
    }

    sort(q_array.begin() + 1, q_array.end());

    // Initialize components and their hashes
    for (int i = 1; i <= n; ++i) {
        if (p[i] != q_array[i]) {
            diffs[i][p[i]]++;
            diffs[i][q_array[i]]--;
             if (diffs[i][p[i]] == 0) diffs[i].erase(p[i]);
             if (diffs[i].count(q_array[i]) && diffs[i][q_array[i]] == 0) diffs[i].erase(q_array[i]);
        }
        if (!diffs[i].empty()) {
             component_hashes[i] = get_hash(diffs[i]);
             hash_to_total_size[component_hashes[i]]++;
             bad_components_count++;
        }
    }

    // Initialize total_q4_pairs
    for(auto const& [hash, size] : hash_to_total_size) {
        pair<long long, long long> comp_hash = get_complement_hash({ {1,1} }); // Placeholder to call func
        // This is tricky, need to generate comp_hash without a map.
        // Let's compute it from a dummy map for now, though this is inefficient.
        // A better way would be a function that computes complement hash directly from hash.
        // But for simplicity of fix:
        map<int,int> dummy_map; // Create a map that would produce `hash`. Can't do easily.
                                // Instead, we iterate and match.
    }
    // Simple initialization loop
    map<pair<long long, long long>, bool> visited;
    for(auto const& [hash, size] : hash_to_total_size) {
        if (visited[hash]) continue;
        pair<long long, long long> comp_hash = get_complement_hash(diffs[dsu.find(1)]); // Find a component with this hash
        
        int comp_root = -1;
        for(int i=1; i<=n; ++i){ if(component_hashes[i] == hash) {comp_root = i; break;} }
        if(comp_root == -1) continue;
        comp_hash = get_complement_hash(diffs[comp_root]);

        if (hash != comp_hash) {
             total_q4_pairs += size * hash_to_total_size[comp_hash];
        } else {
             total_q4_pairs += size * (size - 1) / 2;
        }
        visited[hash] = true;
        visited[comp_hash] = true;
    }


    for (int k = 0; k < q; ++k) {
        int type;
        cin >> type;
        if (type == 1) {
            int u, v;
            cin >> u >> v;
            int root_u = dsu.find(u);
            int root_v = dsu.find(v);
            
            if (p[u] == p[v]) continue;

            if (root_u != root_v) {
                modify_component_diff(root_u, p[u], -1);
                modify_component_diff(root_u, p[v], 1);
                modify_component_diff(root_v, p[v], -1);
                modify_component_diff(root_v, p[u], 1);
            }
            swap(p[u], p[v]);
        } else if (type == 2) {
            int u, v;
            cin >> u >> v;
            int root_u = dsu.find(u);
            int root_v = dsu.find(v);

            if (root_u != root_v) {
                if (dsu.sz[root_u] < dsu.sz[root_v]) swap(root_u, root_v);

                // --- Remove old components' contributions ---
                long long old_size_u = dsu.sz[root_u];
                pair<long long, long long> old_hash_u = component_hashes[root_u];
                if(!diffs[root_u].empty()) {
                     pair<long long, long long> old_comp_hash_u = get_complement_hash(diffs[root_u]);
                     update_pairs(old_hash_u, old_comp_hash_u, hash_to_total_size[old_hash_u], hash_to_total_size[old_hash_u] - old_size_u);
                     if(old_hash_u != old_comp_hash_u)
                        update_pairs(old_comp_hash_u, old_hash_u, hash_to_total_size[old_comp_hash_u], hash_to_total_size[old_comp_hash_u]);
                     hash_to_total_size[old_hash_u] -= old_size_u;
                     bad_components_count--;
                }

                long long old_size_v = dsu.sz[root_v];
                pair<long long, long long> old_hash_v = component_hashes[root_v];
                 if(!diffs[root_v].empty()) {
                     pair<long long, long long> old_comp_hash_v = get_complement_hash(diffs[root_v]);
                     update_pairs(old_hash_v, old_comp_hash_v, hash_to_total_size[old_hash_v], hash_to_total_size[old_hash_v] - old_size_v);
                     if(old_hash_v != old_comp_hash_v)
                        update_pairs(old_comp_hash_v, old_hash_v, hash_to_total_size[old_comp_hash_v], hash_to_total_size[old_comp_hash_v]);
                     hash_to_total_size[old_hash_v] -= old_size_v;
                     bad_components_count--;
                }
                
                // --- Merge ---
                dsu.parent[root_v] = root_u;
                dsu.sz[root_u] += dsu.sz[root_v];
                
                for (auto const& [val, count] : diffs[root_v]) {
                    diffs[root_u][val] += count;
                    if (diffs[root_u][val] == 0) diffs[root_u].erase(val);
                }
                diffs[root_v].clear();
                
                // --- Add new component's contribution ---
                long long new_size = dsu.sz[root_u];
                pair<long long, long long> new_hash = get_hash(diffs[root_u]);
                component_hashes[root_u] = new_hash;

                if(!diffs[root_u].empty()){
                    pair<long long, long long> new_comp_hash = get_complement_hash(diffs[root_u]);
                    hash_to_total_size[new_hash] += new_size;
                    update_pairs(new_hash, new_comp_hash, hash_to_total_size[new_hash] - new_size, hash_to_total_size[new_hash]);
                     if(new_hash != new_comp_hash)
                        update_pairs(new_comp_hash, new_hash, hash_to_total_size[new_comp_hash], hash_to_total_size[new_comp_hash]);
                    bad_components_count++;
                }

            }
        } else if (type == 3) {
            cout << (bad_components_count == 0 ? "DA\n" : "NE\n");
        } else { // type 4
            cout << total_q4_pairs << "\n";
        }
    }

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 14 / 14