Submission #1158323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158323		nrg_studio	Zamjene (COCI16_zamjene)	C++20	42 / 140	3385 ms	130896 KiB

zamjene

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define v vector

const int MAX_N = 1e6;
ll hsh[MAX_N], h[MAX_N];
int sz[MAX_N], par[MAX_N];
int p[MAX_N], q[MAX_N];
map<ll,int> paired;
ll pairs = 0;

int get(int x) {return (par[x]==x ? x : par[x]=get(par[x]));}
void upd_pair(int a, int m) {
    if (hsh[a]) {
        pairs += (ll)m*sz[a]*paired[-hsh[a]];
        paired[hsh[a]] += m*sz[a];
    }
}
void unite(int x, int y) {
    int a = get(x), b = get(y);
    if (a==b) {return;}

    upd_pair(a,-1); upd_pair(b,-1);

    if (sz[a]<sz[b]) {swap(a,b);}
    par[b] = a; sz[a] += sz[b]; hsh[a] += hsh[b];
    // merge sets
    
    upd_pair(a,1);
}

void swp(int x, int y) {
    int a = get(x), b = get(y);
    if (a==b) {return;}
    
    upd_pair(a,-1); upd_pair(b,-1);
    hsh[a] += h[p[y]]-h[p[x]];
    hsh[b] += h[p[x]]-h[p[y]];

    swap(p[x],p[y]);
    upd_pair(a,1); upd_pair(b,1);
}

void pre() {
    mt19937 gen(std::chrono::steady_clock::now().time_since_epoch().count());
    F0R(i,MAX_N) {h[i] = uniform_int_distribution<ll>(0,INT32_MAX)(gen);}

    F0R(i,MAX_N) {
        par[i] = i;
        sz[i] = 1;
    }
    // c1+c2=p1+p2; c1-p1 = -(c2-p2)
    // let hash be c-p
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    pre();
    int n, nq; cin >> n >> nq;
    F0R(i,n) {
        cin >> p[i];
        q[i] = p[i];
    }
    sort(q,q+n);

    F0R(i,n) {
        hsh[i] = h[p[i]]-h[q[i]];
    }
    F0R(i,n) {upd_pair(i,1);}

    //cout<<pairs<<'\n';

    while (nq--) {
        int t; cin >> t;
        if (t==1) {
            int a, b; cin >> a >> b;
            swp(--a,--b);
        } else if (t==2) {
            int a, b; cin >> a >> b;
            unite(--a,--b);
        } else if (t==3) {
            cout << (pairs ? "NE" : "DA") << '\n';
        } else {
            cout << pairs << '\n';
        }
    }

    /*
    dsu for links
    set of elements in comp = set of positions in comp, then it's good
    maintain which nums are missing from each component
    check for first missing check for what component it's in do hashes equal
    if so then add 1 to type 4 query thing

    upd that whenever updating a component

    1) if comp of a and b are different, update their components by 
    deleting corresponding pairs, change hashes, upd corresponding pairs
    xor hashing is easiest

    2) delete corresponding pairs merge upd pairs

    3) count if all components are good

    4) return # pairs (return size of paired set / 2)

    upd pair:
    maintain set of positions for each, delete from set if is contained
    query set and check the position of that element and check hash
    and add/remove from paired set

    swap:
    if they were in their sets, delete them
    and if the new thing is in the set, add them back
    */
}

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