Submission #1239376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239376		orcslop	Zamjene (COCI16_zamjene)	C++20	84 / 140	6083 ms	283208 KiB

zamjene

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

// Use fast I/O
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

// DSU parent array
std::vector<int> parent;
// Initial array p and sorted array q
std::vector<int> p, q;
// For each component root: map of values it has, map of values it needs, and its size
std::vector<std::map<int, int>> has, needs;
std::vector<int> sz;

// Hashing parameters
long long B1, B2, M;
std::vector<long long> p1, p2;

// Global state variables for O(1) queries
long long good_components;
long long total_components;
long long type4_pairs;
// Map to store sum of component sizes for each hash pair
std::map<std::pair<long long, long long>, long long> hash_to_size_sum;

// --- Hashing Functions ---

// Function to precompute powers for hashing
void precompute_powers(int n) {
    p1.resize(n + 1);
    p2.resize(n + 1);
    p1[0] = p2[0] = 1;
    for (int i = 1; i <= n; ++i) {
        p1[i] = (p1[i - 1] * B1) % M;
        p2[i] = (p2[i - 1] * B2) % M;
    }
}

// Function to calculate the hash of a diff map
std::pair<long long, long long> get_hash(const std::map<int, int>& diff) {
    long long h1 = 0, h2 = 0;
    for (auto const& [val, count] : diff) {
        if (count == 0) continue;
        long long term1 = (p1[val] * std::abs(count)) % M;
        long long term2 = (p2[val] * std::abs(count)) % M;
        if (count > 0) {
            h1 = (h1 + term1) % M;
            h2 = (h2 + term2) % M;
        } else {
            h1 = (h1 - term1 + M) % M;
            h2 = (h2 - term2 + M) % M;
        }
    }
    return {h1, h2};
}

// --- DSU and State Management ---

// DSU find operation with path compression
int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

// Helper to calculate the difference map for a component
std::map<int, int> get_diff_map(int root) {
    std::map<int, int> diff;
    for (auto const& [val, count] : has[root]) {
        diff[val] += count;
    }
    for (auto const& [val, count] : needs[root]) {
        diff[val] -= count;
    }
    return diff;
}

// Function to update global statistics when a component's state changes
void update_stats(int root, int add) {
    auto diff = get_diff_map(root);
    bool is_good = true;
    for (auto const& [val, count] : diff) {
        if (count != 0) {
            is_good = false;
            break;
        }
    }

    if (is_good) {
        good_components += add;
    } else {
        auto h = get_hash(diff);
        auto complement_h = std::make_pair((M - h.first) % M, (M - h.second) % M);
        long long component_size = sz[root];

        if (add == -1) { // Remove contribution
            // First, remove this component's effect on the total pairs
            if (hash_to_size_sum.count(complement_h)) {
                type4_pairs -= component_size * hash_to_size_sum[complement_h];
            }
            // Then, update the map of hash -> size sums
            hash_to_size_sum[h] -= component_size;
        } else { // Add contribution
            // First, update the map of hash -> size sums
            hash_to_size_sum[h] += component_size;
            // Then, add this component's new contribution to total pairs
            if (hash_to_size_sum.count(complement_h)) {
                type4_pairs += component_size * hash_to_size_sum[complement_h];
            }
        }
    }
}


// DSU unite operation
void unite_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        // Remove old components from global stats
        update_stats(a, -1);
        update_stats(b, -1);

        // Standard DSU merge by size
        if (sz[a] < sz[b]) std::swap(a, b);

        // Merge maps
        for (auto const& [val, count] : has[b]) {
            has[a][val] += count;
        }
        for (auto const& [val, count] : needs[b]) {
            needs[a][val] += count;
        }
        
        has[b].clear();
        needs[b].clear();

        parent[b] = a;
        sz[a] += sz[b];
        total_components--;

        // Add new merged component to global stats
        update_stats(a, 1);
    }
}


int main() {
    fast_io();

    int n, q_count;
    std::cin >> n >> q_count;

    p.resize(n + 1);
    q.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> p[i];
        q[i] = p[i];
    }
    std::sort(q.begin() + 1, q.end());

    // Initialize hashing parameters with random bases
    std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
    B1 = std::uniform_int_distribution<long long>(1000001, 1000000006)(rng);
    B2 = std::uniform_int_distribution<long long>(1000001, 1000000006)(rng);
    M = 1000000007;
    precompute_powers(1000000);


    // Initialize DSU and component data
    parent.resize(n + 1);
    std::iota(parent.begin(), parent.end(), 0);
    has.resize(n + 1);
    needs.resize(n + 1);
    sz.assign(n + 1, 1);
    total_components = n;
    good_components = 0;
    type4_pairs = 0;

    for (int i = 1; i <= n; ++i) {
        has[i][p[i]]++;
        needs[i][q[i]]++;
        update_stats(i, 1);
    }

    // Process queries
    for (int k = 0; k < q_count; ++k) {
        int type;
        std::cin >> type;
        if (type == 1) {
            int u, v;
            std::cin >> u >> v;
            int root_u = find_set(u);
            int root_v = find_set(v);

            // Update stats before the swap
            update_stats(root_u, -1);
            if (root_u != root_v) {
                update_stats(root_v, -1);
            }

            // Update has maps
            has[root_u][p[u]]--;
            has[root_u][p[v]]++;
            if (root_u != root_v) {
                has[root_v][p[v]]--;
                has[root_v][p[u]]++;
            }
            
            // Perform swap
            std::swap(p[u], p[v]);

            // Update stats after the swap
            update_stats(root_u, 1);
            if (root_u != root_v) {
                update_stats(root_v, 1);
            }

        } else if (type == 2) {
            int u, v;
            std::cin >> u >> v;
            unite_sets(u, v);
        } else if (type == 3) {
            if (good_components == total_components) {
                std::cout << "DA\n";
            } else {
                std::cout << "NE\n";
            }
        } else if (type == 4) {
            std::cout << type4_pairs << "\n";
        }
    }

    return 0;
}

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