Submission #1158336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158336		nrg_studio	Zamjene (COCI16_zamjene)	C++20	98 / 140	694 ms	105448 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];
unordered_map<ll,int> paired;
ll pairs = 0, notgood = 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];
        notgood += m;
    }
}
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) {
        upd_pair(a,-1); upd_pair(b,-1);
        hsh[a] += h[p[y]]-h[p[x]];
        hsh[b] += h[p[x]]-h[p[y]];

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


    swap(p[x],p[y]);
}

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

int j=0;
    F0R(i,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) {
            j++;
            cout << (notgood ? "NE" : "DA") << '\n';
        } else {
            j++;
            cout << pairs << '\n';
        }
        //if (j==154) {cout<<i<<'\n';}
    }
}

• 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: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14