Submission #1075322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075322		Neco_arc	Zamjene (COCI16_zamjene)	C++17	140 / 140	3371 ms	192352 KiB

zamjene

#include <bits/stdc++.h>
#ifdef LOCAL
#include <bits/debug.hpp>
#endif // LOCAL

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Zamjene"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 1e6 + 7
#define int long long

using namespace std;

const ll HASH = 1234577;
const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n, q;
int a[maxn], b[maxn];
ll Rnd[maxn];

struct DSU {
    int lab[maxn], tplt;
    ll S[maxn], Val;
    map<ll, int> P;

    void init() {
        tplt = n;
        fi(i, 1, n) Change(0, 1);
        fi(i, 1, n) {
            lab[i] = -1;
            update(i, Rnd[a[i]] - Rnd[b[i]]);
        }
    }

    void Change(ll val, ll w) {
        if(val != 0) Val += P[-val] * w;
        P[val] += w;
    }

    void update(int u, ll w) {
        Change(S[u], lab[u]);
        S[u] += w;
        Change(S[u], -lab[u]);
    }

    bool good() { return P[0] == n; }

    int get_rt(int u) {
        return lab[u] < 0 ? u : lab[u] = get_rt(lab[u]);
    }

    void uni(int u, int v) {
        int p = get_rt(u), q = get_rt(v); if(p == q) return;
        if(lab[p] > lab[q]) swap(p, q);

        --tplt;
        ll Sum = S[p] + S[q];
        update(q, -S[q]), update(p, -S[p]);
        P[0] -= -(lab[p] + lab[q]);

        lab[p] += lab[q], lab[q] = p;
        S[p] = Sum, Change(S[p], -lab[p]);
    }

} Dsu;

void solve()
{

    cin >> n >> q;
    fi(i, 1, n) cin >> a[i], b[i] = a[i];
    sort(b + 1, b + 1 + n);

    Dsu.init();

    fi(i, 1, q) {
        int type, x, y; cin >> type;
        if(type <= 2) cin >> x >> y;

        if(type == 1) {
            int u = Dsu.get_rt(x), v = Dsu.get_rt(y);
            Dsu.update(u, Rnd[a[y]] - Rnd[a[x]]);
            Dsu.update(v, Rnd[a[x]] - Rnd[a[y]]);
            swap(a[x], a[y]);
        }

        if(type == 2) {
            Dsu.uni(x, y);
        }

        if(type == 3) {
            cout << (Dsu.good() ? "DA\n" : "NE\n");
        }

        if(type == 4) {
            cout << Dsu.Val << '\n';
        }

    }


}


main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }

    Rnd[0] = 1;
    fi(i, 1, maxn - 2) Rnd[i] = Rnd[i - 1] * HASH;

    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message (stderr)

zamjene.cpp:118:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  118 | main()
      | ^~~~
zamjene.cpp: In function 'int main()':
zamjene.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zamjene.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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