Submission #1239388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239388		orcslop	Zamjene (COCI16_zamjene)	C++20	140 / 140	5257 ms	359016 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 int MAX_VAL = 1000001;

vector<long long> p1_powers(MAX_VAL);
vector<long long> p2_powers(MAX_VAL);

// 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;

void precompute_powers() {
    p1_powers[0] = 1;
    p2_powers[0] = 1;
    for (int i = 1; i < MAX_VAL; ++i) {
        p1_powers[i] = (p1_powers[i - 1] * P1) % M1;
        p2_powers[i] = (p2_powers[i - 1] * P2) % M2;
    }
}

// Helper to manage modulo arithmetic for negative results
long long norm(long long val, long long mod) {
    return (val % mod + mod) % mod;
}

// Updates the total pair count when a group's total size changes
void change_pair_contribution(pair<long long, long long> hash, long long size_delta) {
    if (hash == make_pair(0LL, 0LL)) return;

    pair<long long, long long> comp_hash = {-hash.first, -hash.second};
    comp_hash.first = norm(comp_hash.first, M1);
    comp_hash.second = norm(comp_hash.second, M2);

    long long old_size_h = hash_to_total_size[hash];
    long long new_size_h = old_size_h + size_delta;

    if (hash != comp_hash) {
        long long size_ch = hash_to_total_size[comp_hash];
        total_q4_pairs += size_delta * size_ch;
    } else {
        total_q4_pairs -= old_size_h * (old_size_h - 1) / 2;
        total_q4_pairs += new_size_h * (new_size_h - 1) / 2;
    }
    hash_to_total_size[hash] = new_size_h;
}

// Incrementally updates a component's diff map and hash
void update_diff_and_hash(int root, int val, int count_delta) {
    int old_count = diffs[root][val];
    int new_count = old_count + count_delta;

    long long h1_delta = norm((long long)(new_count - old_count) * p1_powers[val], M1);
    long long h2_delta = norm((long long)(new_count - old_count) * p2_powers[val], M2);

    component_hashes[root].first = norm(component_hashes[root].first + h1_delta, M1);
    component_hashes[root].second = norm(component_hashes[root].second + h2_delta, M2);

    diffs[root][val] = new_count;
    if (new_count == 0) {
        diffs[root].erase(val);
    }
}

// Removes a component's contribution from global stats
void remove_from_stats(int root) {
    if (diffs[root].empty()) return;
    bad_components_count--;
    change_pair_contribution(component_hashes[root], -dsu.sz[root]);
}

// Adds a component's contribution to global stats
void add_to_stats(int root) {
    if (diffs[root].empty()) return;
    bad_components_count++;
    change_pair_contribution(component_hashes[root], dsu.sz[root]);
}


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

    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 incrementally
    for (int i = 1; i <= n; ++i) {
        if (p[i] != q_array[i]) {
            update_diff_and_hash(i, p[i], 1);
            update_diff_and_hash(i, q_array[i], -1);
        }
    }
    
    // Initialize global counts
    for(int i=1; i<=n; ++i) {
        if(!diffs[i].empty()){
            bad_components_count++;
            hash_to_total_size[component_hashes[i]]++;
        }
    }
    
    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 = {-hash.first, -hash.second};
        comp_hash.first = norm(comp_hash.first, M1);
        comp_hash.second = norm(comp_hash.second, M2);
        
        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) {
                remove_from_stats(root_u);
                remove_from_stats(root_v);
                
                update_diff_and_hash(root_u, p[u], -1);
                update_diff_and_hash(root_u, p[v], 1);
                update_diff_and_hash(root_v, p[v], -1);
                update_diff_and_hash(root_v, p[u], 1);
                
                add_to_stats(root_u);
                add_to_stats(root_v);
            }
            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_from_stats(root_u);
                remove_from_stats(root_v);
                
                dsu.parent[root_v] = root_u;
                dsu.sz[root_u] += dsu.sz[root_v];
                
                for (auto const& [val, count] : diffs[root_v]) {
                    update_diff_and_hash(root_u, val, count);
                }
                
                add_to_stats(root_u);
            }
        } 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: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14