oj.uz

답안 #653164

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653164 2022-10-25T22:41:17 Z gozonite Zamjene (COCI16_zamjene) C++14
140 / 140
 2543 ms 141496 KB 
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>
#include <queue>
#include <tuple>
#include <cmath>
#include <cctype>
#include <stack>
#include <cassert>
#include <iomanip>
#include <random>
#include <chrono>
using namespace std;
using ll = long long;
ll P = (1LL<<61LL) - 1LL;

int N, Q;
ll p[1000001], goal[1000001];
ll ph[1000001];
ll ah[1000001], gh[1000001];
unordered_map<ll, ll> hcnt;
ll par[1000001], cnt[1000001];
ll pres = 0;
ll badSets = 0;

void gen_hash() {
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    mt19937_64 mt(seed);
    for (int i = 1; i <= N; i++) ph[i] = mt() % P;
}

int get(int x) {
    return x==par[x] ? x : par[x] = get(par[x]);
}
void unite(int a, int b) {
    assert(a == get(a) && b == get(b) && a != b);
    if (cnt[a] < cnt[b]) swap(a, b);
    if (ah[a] != gh[a]) {
        badSets--;
        hcnt[(ah[a] - gh[a]+P)%P] -= cnt[a];
        pres -= cnt[a]*hcnt[(gh[a] - ah[a]+P)%P];
    }
    if (ah[b] != gh[b]) {
        badSets--;
        hcnt[(ah[b] - gh[b]+P)%P] -= cnt[b];
        pres -= cnt[b]*hcnt[(gh[b] - ah[b]+P)%P];
    }
    par[b] = a;
    cnt[a] += cnt[b], cnt[b] = 0;
    ah[a] = (ah[a] + ah[b]) % P;
    gh[a] = (gh[a] + gh[b]) % P;

    if (ah[a] != gh[a]) {
        badSets++;
        hcnt[(ah[a] - gh[a]+P)%P] += cnt[a];
        pres += cnt[a]*hcnt[(gh[a] - ah[a]+P)%P];
    }
}

int main() {
    cin >> N >> Q;
    for (int i = 1; i <= N; i++) {
        cin >> p[i]; goal[i] = p[i];
    }
    sort(goal+1, goal+1+N);
    gen_hash();
    for (int i = 1; i <= N; i++) {
        par[i] = i, cnt[i] = 1;
        ah[i] = ph[p[i]], gh[i] = ph[goal[i]];
        if (ah[i] != gh[i]) {
            badSets++;
            hcnt[(ah[i] - gh[i] + P)%P] += cnt[i];
            pres += cnt[i]*hcnt[(gh[i]-ah[i]+P)%P];
        }
    }
    for (int q = 1; q <= Q; q++) {
        int t; cin >> t;
        if (t == 1) {
            int A, B; cin >> A >> B;
            ll av = p[A], bv = p[B];
            swap(p[A], p[B]);
            A = get(A); B = get(B);
            if (A == B) continue; // shouldn't change the outcome of the program but useful to eliminate redundancy
            // remove from answers to 3 and 4
            if (ah[A] != gh[A]) {
                badSets--;
                hcnt[(ah[A] - gh[A]+P)%P] -= cnt[A];
                pres -= cnt[A]*hcnt[(gh[A] - ah[A]+P)%P];
            }
            if (ah[B] != gh[B]) {
                badSets--;
                hcnt[(ah[B] - gh[B]+P)%P] -= cnt[B];
                pres -= cnt[B]*hcnt[(gh[B] - ah[B]+P)%P];
            }

            // adjust data structure
            ah[A] = (ah[A] - ph[av] + ph[bv]) % P;
            if (ah[A] < 0) ah[A] += P;
            ah[B] = (ah[B] - ph[bv] + ph[av]) % P;
            if (ah[B] < 0) ah[B] += P;

            // add back to answers to 3 and 4
            if (ah[A] != gh[A]) {
                badSets++;
                hcnt[(ah[A] - gh[A]+P)%P] += cnt[A];
                pres += cnt[A]*hcnt[(gh[A] - ah[A]+P)%P];
            }
            if (ah[B] != gh[B]) {
                badSets++;
                hcnt[(ah[B] - gh[B]+P)%P] += cnt[B];
                pres += cnt[B]*hcnt[(gh[B] - ah[B]+P)%P];
            }

        } else if (t == 2) { // combine dsu's with A and B
            int A, B; cin >> A >> B;
            A = get(A); B = get(B);
            if (A == B) continue;
            unite(A, B);

        } else if (t == 3) {
            cout << (badSets==0 ? "DA" : "NE") << endl;
        } else if (t == 4) {
            cout << pres << endl;
        }

        // cout << "after applying query " << q << ": " << endl;
        // cout << "par, cnt: " << endl;
        // for (int i = 1; i <= N; i++) cout << par[i] << " "; cout << endl;
        // for (int i = 1; i <= N; i++) cout << cnt[i] << " "; cout << endl;
        // for (int i = 1; i <= N; i++) cout << ah[i] << " "; cout << endl;
        // for (int i = 1; i <= N; i++) cout << gh[i] << " "; cout << endl;
        // cout << "badsets, pres: " << badSets << " " << pres << endl;
        // for (auto pp : hcnt) cout << pp.first << " " << pp.second << endl;
    }


}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 316 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 324 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 456 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 320 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 2 ms 468 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 980 KB Output is correct
2 Correct 15 ms 1108 KB Output is correct
3 Correct 15 ms 1020 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 7268 KB Output is correct
2 Correct 188 ms 8528 KB Output is correct
3 Correct 192 ms 10328 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1586 ms 49808 KB Output is correct
2 Correct 2422 ms 118304 KB Output is correct
3 Correct 2543 ms 141496 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1884 ms 94568 KB Output is correct
2 Correct 2305 ms 111488 KB Output is correct
3 Correct 1792 ms 109724 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1651 ms 72060 KB Output is correct
2 Correct 2065 ms 97016 KB Output is correct
3 Correct 1822 ms 109624 KB Output is correct