oj.uz

Submission #776080

# Submission time Handle Problem Language Result Execution time Memory
776080 2023-07-07T09:26:47 Z Nhoksocqt1 Zamjene (COCI16_zamjene) C++17
126 / 140
 6000 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
    inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
    inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 1000006;
const int NMOD = 2;

const int BASE = 2000006;
const int MOD[] = {int(1e9) + 2277, int(1e9) + 5277, int(1e9) + 8277, int(1e9) + 9277};

ll pw[NMOD][MAXN];

struct Hash {
    ll value[NMOD];

    Hash(int c = 0) {
        for (int i = 0; i < NMOD; ++i)
            value[i] = c;
    }

    Hash& operator += (const Hash &h) {
        for (int i = 0; i < NMOD; ++i) {
            if((value[i] += h.value[i]) >= MOD[i])
                value[i] -= MOD[i];
        }

        return (*this);
    }

    Hash operator + (const Hash &h) const {
        Hash res = (*this);
        return res += h;
    }

    Hash& operator -= (const Hash &h) {
        for (int i = 0; i < NMOD; ++i) {
            if((value[i] -= h.value[i]) < 0)
                value[i] += MOD[i];
        }

        return (*this);
    }

    Hash operator - (const Hash &h) const {
        Hash res = (*this);
        return res -= h;
    }

    Hash operator * (int k) const {
        Hash res;
        for (int i = 0; i < NMOD; ++i)
            res.value[i] = value[i] * pw[i][k] % MOD[i];

        return res;
    }

    bool operator == (const Hash &h) const {
        for (int i = 0; i < NMOD; ++i) {
            if(value[i] != h.value[i])
                return false;
        }

        return true;
    }

    bool operator < (const Hash &h) const {
        for (int i = 0; i < NMOD; ++i) {
            if(value[i] != h.value[i])
                return value[i] < h.value[i];
        }

        return false;
    }

} hashVal[MAXN], rhashVal[MAXN];

int lab[MAXN];
set<int> S[MAXN];
vector<int> adj[MAXN], idx;
map<Hash, int> Map;
map<int, int> cnt[MAXN];
int p[MAXN], q[MAXN], cntBadComp, nArr, numQuery;
ll result;

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

int getSize(int u) {
    return -lab[root(u)];
}

Hash goodCompHash;
bool isBadComp(int u) {
    return (!(hashVal[u] == rhashVal[u]));

    bool check = !(hashVal[u] == rhashVal[u]);
    u = root(u);
    for (auto it : S[u]) {
        if(cnt[u][it] != 0) {
            assert(check);
            return true;
        }
    }

    assert(!check);
    return false;
}

bool checkFor(int u, int v) {
    u = root(u), v = root(v);
    if(u == v || !isBadComp(u) || !isBadComp(v))
        return false;

    for (auto it : S[v]) {
        if(cnt[v][it] != -cnt[u][it])
            return false;
    }

    for (auto it : S[u]) {
        if(cnt[u][it] != -cnt[v][it])
            return false;
    }

    return true;
}

ll calcBrute(int u) {
    u = root(u);
    if(!isBadComp(u))
        return 0;

    ll res(0);
    for (int v = 1; v <= nArr; ++v) {
        if(root(v) != v)
            continue;

        res += 1LL * getSize(v) * checkFor(u, v);
    }

    return res;
}

ll calc(int u) {
    u = root(u);
    if(!isBadComp(u))
        return 0;

    //return calcBrute(u);
    //assert(Map[rhashVal[u]] == calcBrute(u));
    return Map[rhashVal[u]];
}

void modifyVal(int u, int k, int val) {
    u = root(u);
    cntBadComp -= isBadComp(u);
    result -= 1LL * getSize(u) * calc(u);

    cnt[u][k] += val;
    Map[hashVal[u]] -= getSize(u);
    if(val > 0) {
        hashVal[u] += Hash(1) * k;
        rhashVal[u] -= Hash(1) * k;
        //cout << "+ " << k << ' ' << u << ' ' << (Hash(1) * k).value[0] << ' ' << hashVal[u].value[0] << '\n';
    } else {
        hashVal[u] -= Hash(1) * k;
        rhashVal[u] += Hash(1) * k;
        //cout << "- " << k << ' ' << u << ' ' << (Hash(1) * k).value[0] << ' ' << hashVal[u].value[0] << '\n';
    }

    S[u].insert(k);
    Map[hashVal[u]] += getSize(u);
    cntBadComp += isBadComp(u);
    result += 1LL * getSize(u) * calc(u);
}

void removeComp(int u) {
    u = root(u);
    cntBadComp -= isBadComp(u);
    result -= 1LL * getSize(u) * calc(u);
    Map[hashVal[u]] -= getSize(u);
    hashVal[u] = 0, rhashVal[u] = 1;
    S[u].clear(), cnt[u].clear();
}

void swapPos(int u, int v) {
    int ru(root(u)), rv(root(v));
    if(ru == rv) {
        swap(p[u], p[v]);
        return;
    }

    modifyVal(ru, p[u], -1), modifyVal(rv, p[v], -1);
    //cout << ','; exit(0);

    swap(p[u], p[v]);
    modifyVal(ru, p[u], 1), modifyVal(rv, p[v], 1);
}

bool join(int u, int v) {
    u = root(u), v = root(v);
    if(u == v)
        return (false);

    if(lab[u] > lab[v])
        swap(u, v);

    cntBadComp -= isBadComp(u);
    result -= 1LL * getSize(u) * calc(u);
    Map[hashVal[u]] -= getSize(u); Hash tmp(hashVal[u]); hashVal[u] = 0; cnt[u][p[u]] += 1e9;
    removeComp(v); cnt[u][p[u]] -= 1e9; hashVal[u] = tmp;
    lab[u] += lab[v];
    lab[v] = u;

    for (int it = 0; it < sz(adj[v]); ++it) {
        int c(adj[v][it]);
        S[u].insert(p[c]), S[u].insert(q[c]);
        ++cnt[u][p[c]], --cnt[u][q[c]];
        hashVal[u] += Hash(1) * p[c] - Hash(1) * q[c];
        rhashVal[u] -= Hash(1) * p[c] - Hash(1) * q[c];
        adj[u].push_back(c);
    }

    Map[hashVal[u]] += getSize(u);
    cntBadComp += isBadComp(u);
    result += 1LL * getSize(u) * calc(u);
    return (true);
}

void prepare(void) {
    for (int i = 0; i < NMOD; ++i) {
        pw[i][0] = 1;
        for (int j = 1; j <= nArr; ++j)
            pw[i][j] = pw[i][j - 1] * BASE % MOD[i];
    }

    goodCompHash = 0;
    for (int j = 1; j <= nArr; ++j)
        goodCompHash += Hash(nArr) * j;
}

void process() {
    cin >> nArr >> numQuery; //nArr = 2000, numQuery = 10000;
    for (int i = 1; i <= nArr; ++i) {
        cin >> p[i];
        //p[i] = Random(1, nArr); cout << p[i] << " \n"[i == nArr];
        idx.push_back(p[i]);
        lab[i] = -1;
    }

    sort(idx.begin(), idx.end());
    idx.erase(unique(idx.begin(), idx.end()), idx.end());
    for (int i = 1; i <= nArr; ++i)
        p[i] = q[i] = upper_bound(idx.begin(), idx.end(), p[i]) - idx.begin();

    prepare();
    sort(q + 1, q + nArr + 1);
    for (int i = 1; i <= nArr; ++i) {
        cntBadComp += (p[i] != q[i]);
        ++cnt[i][p[i]], --cnt[i][q[i]];
        hashVal[i] = goodCompHash + Hash(1) * p[i] - Hash(1) * q[i];
        rhashVal[i] = goodCompHash - Hash(1) * p[i] + Hash(1) * q[i];
        //cout << "+ " << p[i] << ' ' << i << '\n';
        //cout << "- " << q[i] << ' ' << i << '\n';
        adj[i].push_back(i);
        S[i].insert(p[i]), S[i].insert(q[i]);
        ++Map[hashVal[i]];
        result += calc(i);
    }

    //cout << goodCompHash.value[0] << '\n';
    for (int t = 0; t < numQuery; ++t) {
        int type, A, B;
        cin >> type;
        //type = Random(1, 4); cout << type << ' ';
        if(type <= 2) {
            cin >> A >> B;
            //A = Random(1, nArr - 1), B = Random(A + 1, nArr); cout << A << ' ' << B << '\n';
        }

        if(type == 1) {
            swapPos(A, B);
        } else
            if(type == 2) {
                join(A, B);
            } else
                if(type == 3) {
                    cout << (cntBadComp == 0 ? "DA" : "NE") << '\n';
                } else {
                    cout << result << '\n';
                }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    process();
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 149096 KB Output is correct
2 Correct 67 ms 149000 KB Output is correct
3 Correct 61 ms 148988 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 148988 KB Output is correct
2 Correct 58 ms 149000 KB Output is correct
3 Correct 60 ms 149012 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 149024 KB Output is correct
2 Correct 63 ms 149080 KB Output is correct
3 Correct 60 ms 149068 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 149132 KB Output is correct
2 Correct 61 ms 149076 KB Output is correct
3 Correct 58 ms 149228 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 149280 KB Output is correct
2 Correct 60 ms 149300 KB Output is correct
3 Correct 62 ms 149388 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 151148 KB Output is correct
2 Correct 70 ms 151212 KB Output is correct
3 Correct 74 ms 151180 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 173048 KB Output is correct
2 Correct 296 ms 179512 KB Output is correct
3 Correct 415 ms 185328 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3053 ms 293740 KB Output is correct
2 Execution timed out 6051 ms 442900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3789 ms 483696 KB Output is correct
2 Correct 5492 ms 524288 KB Output is correct
3 Correct 3075 ms 421924 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2348 ms 415328 KB Output is correct
2 Correct 4251 ms 506284 KB Output is correct
3 Correct 3111 ms 422276 KB Output is correct