oj.uz

답안 #735467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
735467 2023-05-04T07:47:35 Z GrindMachine Zamjene (COCI16_zamjene) C++17
14 / 140
 6000 ms 90656 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)


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;

struct DSU {
    vector<int> par, rankk, siz;
    vector<ll> hsh;
    map<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;
        siz[u] += siz[v];

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

    map<ll, ll> mp;
    rep1(i, n) {
        if (mp.count(a[i])) 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;
            if (dsu.same(u, v)) conts;

            swap(a[u], a[v]);

            // dsu.hashes.clear();
            // dsu.cnt = 0;

            // vector<ll> here[n + 5];
            // rep1(i, n) {
            //     ll p = dsu.find(i);
            //     here[p].pb(i);
            // }

            // rep1(p, n) {
            //     if (here[p].empty()) conts;

            //     dsu.hsh[p] = 0;
            //     trav(i, here[p]) {
            //         dsu.hsh[p] += mp[a[i]] - mp[b[i]];
            //         dsu.hsh[p] = (dsu.hsh[p] % MOD + MOD) % MOD;
            //     }

            //     ll siz = sz(here[p]);
            //     dsu.cnt += siz * dsu.hashes[MOD - dsu.hsh[p]];
            //     dsu.hashes[dsu.hsh[p]] += siz;
            // }





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

            // dsu.hashes.clear();
            // dsu.cnt = 0;

            // vector<ll> here[n + 5];
            // rep1(i, n) {
            //     ll p = dsu.find(i);
            //     here[p].pb(i);
            // }

            // rep1(p, n) {
            //     if (here[p].empty()) conts;

            //     dsu.hsh[p] = 0;
            //     trav(i, here[p]) {
            //         dsu.hsh[p] += mp[a[i]] - mp[b[i]];
            //         dsu.hsh[p] = (dsu.hsh[p] % MOD + MOD) % MOD;
            //     }

            //     ll siz = sz(here[p]);
            //     dsu.cnt += siz * dsu.hashes[MOD - dsu.hsh[p]];
            //     dsu.hashes[dsu.hsh[p]] += siz;
            // }
        }
        else if (t == 3) {
            bool ans = true;

            vector<ll> here[n + 5];
            rep1(i, n) {
                ll p = dsu.find(i);
                here[p].pb(i);
            }

            rep1(p, n) {
                if (here[p].empty()) conts;

                vector<ll> v1, v2;
                trav(i, here[p]) {
                    v1.pb(a[i]);
                    v2.pb(b[i]);
                }

                sort(all(v1)), sort(all(v2));
                if (v1 != v2) {
                    ans = false;
                }
            }

            if (ans) cout << "DA" << endl;
            else cout << "NE" << endl;

            // if (dsu.hashes[0] == n) cout << "DA" << endl;
            // else cout << "NE" << endl;
        }
        else {
            vector<ll> here[n + 5];
            rep1(i, n) {
                ll p = dsu.find(i);
                here[p].pb(i);
            }

            map<ll, ll> ma;
            ll ans = 0;

            rep1(p, n) {
                if (here[p].empty()) conts;

                ll hsh = 0;
                trav(i, here[p]) {
                    hsh += mp[a[i]] - mp[b[i]];
                    hsh = (hsh % MOD + MOD) % MOD;
                }

                ans += dsu.siz[p] * ma[MOD - hsh];
                ma[hsh] += dsu.siz[p];
            }

            cout << ans << endl;
        }
    }
}

int main()
{
    fastio;

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

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

    return 0;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 408 KB Output is correct
2 Correct 61 ms 404 KB Output is correct
3 Correct 101 ms 500 KB Output is correct

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5155 ms 1336 KB Output is correct
2 Correct 5754 ms 1308 KB Output is correct
3 Execution timed out 6055 ms 1320 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6044 ms 9332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6019 ms 45332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6046 ms 90656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6078 ms 90356 KB Time limit exceeded
2 Halted 0 ms 0 KB -