oj.uz

Submission #735525

# Submission time Handle Problem Language Result Execution time Memory
735525 2023-05-04T09:50:55 Z GrindMachine Zamjene (COCI16_zamjene) C++17
140 / 140
 1240 ms 316072 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://bigprimes.org/ (for generating big prime MOD)
https://gist.github.com/Chillee/3bd6ee4429abb4a2e7c19959fb1490ae#file-hash-table-cpp (custom hash function for gp_hash_table)


sol idea:
dsu + multiset hashing

*/

const ll MOD = 964863244005699737;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

// https://gist.github.com/Chillee/3bd6ee4429abb4a2e7c19959fb1490ae#file-hash-table-cpp
struct chash {
    const int RANDOM = (long long)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
    static unsigned long long hash_f(unsigned long long x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    static unsigned hash_combine(unsigned a, unsigned b) { return a * 31 + b; }
    int operator()(int x) const { return hash_f(x)^RANDOM; }
};

struct DSU {
    vector<int> par, rankk, siz;
    vector<ll> hsh;
    gp_hash_table<ll, ll> hashes;
    ll cnt = 0;

    DSU() {

    }

    DSU(int n) {
        init(n);
    }

    void init(int n) {
        par = vector<int>(n + 1);
        rankk = vector<int>(n + 1);
        siz = vector<int>(n + 1);
        hsh = vector<ll>(n + 1);
        rep(i, n + 1) create(i);
    }

    void create(int u) {
        par[u] = u;
        rankk[u] = 0;
        siz[u] = 1;
    }

    int find(int u) {
        if (u == par[u]) return u;
        else return par[u] = find(par[u]);
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }

    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (rankk[u] == rankk[v]) rankk[u]++;
        if (rankk[u] < rankk[v]) swap(u, v);

        par[v] = u;

        cnt -= siz[u] * hashes[MOD - hsh[u]];
        hashes[hsh[u]] -= siz[u];

        cnt -= siz[v] * hashes[MOD - hsh[v]];
        hashes[hsh[v]] -= siz[v];

        hsh[u] = (hsh[u] + hsh[v]) % MOD;
        siz[u] += siz[v];

        cnt += siz[u] * hashes[MOD - hsh[u]];
        hashes[hsh[u]] += siz[u];
    }
};

void solve(int test_case)
{
    ll n, q; cin >> n >> q;
    vector<ll> a(n + 5);
    rep1(i, n) cin >> a[i];

    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<ll> dist(1, MOD - 1);

    auto b = a;
    sort(b.begin() + 1, b.begin() + n + 1);

    gp_hash_table<ll, ll, chash> mp;
    rep1(i, n) {
        if (mp.find(a[i]) != mp.end()) conts;
        mp[a[i]] = dist(rng);
    }

    DSU dsu(n + 5);

    rep1(i, n) {
        ll v = (mp[a[i]] - mp[b[i]] + MOD) % MOD;
        dsu.hsh[i] = v;
        dsu.cnt += dsu.hashes[MOD - v];
        dsu.hashes[v]++;
    }

    while (q--) {
        ll t; cin >> t;
        if (t == 1) {
            ll u, v; cin >> u >> v;
            ll pu = dsu.find(u), pv = dsu.find(v);


            dsu.cnt -= dsu.siz[pu] * dsu.hashes[MOD - dsu.hsh[pu]];
            dsu.hashes[dsu.hsh[pu]] -= dsu.siz[pu];

            dsu.hsh[pu] += mp[a[v]] - mp[a[u]];
            dsu.hsh[pu] = (dsu.hsh[pu] % MOD + MOD) % MOD;

            dsu.cnt += dsu.siz[pu] * dsu.hashes[MOD - dsu.hsh[pu]];
            dsu.hashes[dsu.hsh[pu]] += dsu.siz[pu];



            dsu.cnt -= dsu.siz[pv] * dsu.hashes[MOD - dsu.hsh[pv]];
            dsu.hashes[dsu.hsh[pv]] -= dsu.siz[pv];

            dsu.hsh[pv] += mp[a[u]] - mp[a[v]];
            dsu.hsh[pv] = (dsu.hsh[pv] % MOD + MOD) % MOD;

            dsu.cnt += dsu.siz[pv] * dsu.hashes[MOD - dsu.hsh[pv]];
            dsu.hashes[dsu.hsh[pv]] += dsu.siz[pv];


            swap(a[u], a[v]);
        }
        else if (t == 2) {
            ll u, v; cin >> u >> v;
            dsu.merge(u, v);
        }
        else if (t == 3) {
            if (dsu.hashes[0] == n) cout << "DA" << endl;
            else cout << "NE" << endl;
        }
        else {
            ll ans = dsu.cnt;
            cout << ans << endl;
        }
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 5 ms 980 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4304 KB Output is correct
2 Correct 49 ms 6452 KB Output is correct
3 Correct 59 ms 13472 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 39648 KB Output is correct
2 Correct 997 ms 168128 KB Output is correct
3 Correct 1240 ms 316072 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 758 ms 112584 KB Output is correct
2 Correct 956 ms 112084 KB Output is correct
3 Correct 753 ms 112540 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 43680 KB Output is correct
2 Correct 830 ms 112380 KB Output is correct
3 Correct 734 ms 112544 KB Output is correct