oj.uz

Submission #1075326

# Submission time Handle Problem Language Result Execution time Memory
1075326 2024-08-26T02:32:31 Z Neco_arc Zamjene (COCI16_zamjene) C++17
140 / 140
 1085 ms 131504 KB 
#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

using namespace std;

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;
    unordered_map<ll, ll> 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';
        }

    }


}


int 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] * base;

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


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


    return 0;
}

Compilation message

zamjene.cpp: In function 'int main()':
zamjene.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 4 ms 8204 KB Output is correct
3 Correct 4 ms 8280 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8540 KB Output is correct
2 Correct 6 ms 8540 KB Output is correct
3 Correct 7 ms 8572 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 11612 KB Output is correct
2 Correct 36 ms 12720 KB Output is correct
3 Correct 46 ms 14572 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 40036 KB Output is correct
2 Correct 927 ms 108528 KB Output is correct
3 Correct 1085 ms 131504 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 67256 KB Output is correct
2 Correct 705 ms 84264 KB Output is correct
3 Correct 519 ms 82360 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 44788 KB Output is correct
2 Correct 505 ms 69740 KB Output is correct
3 Correct 490 ms 82360 KB Output is correct