oj.uz

Submission #626809

# Submission time Handle Problem Language Result Execution time Memory
626809 2022-08-11T20:44:19 Z MilosMilutinovic Zamjene (COCI16_zamjene) C++14
0 / 140
 1785 ms 85860 KB 
/**
 *    author:  wxhtzdy
 *    created: 11.08.2022 22:00:57
**/
#include <bits/stdc++.h>

using namespace std;

class dsu {
  public:
  vector<int> p;
  int n;
  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }
  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }
  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, q;
  cin >> n >> q;
  vector<int> c0(n);
  for (int i = 0; i < n; i++) {
    cin >> c0[i];
  }
  auto c1 = c0;
  sort(c1.begin(), c1.end());
  vector<long long> pw(1, 1);
  const int BASE = 77777;
  for (int i = 1; i <= c1.back(); i++) {
    pw.push_back((pw.back() * BASE) % 998244353);
  }
  dsu d(n);
  vector<long long> f0(n);
  vector<long long> f1(n);
  map<long long, int> cnt;
  long long ans = 0;
  auto Add = [&](int x, int c) {
    if (x != 0) {
      ans += cnt[-x] * 1LL * c;
    }
    cnt[x] += c;
  }; 
  auto Remove = [&](int x, int c) {
    if (x != 0) {
      ans -= cnt[-x] * 1LL * c;
    }
    cnt[x] -= c;
  };
  for (int i = 0; i < n; i++) {
    f0[i] = pw[c0[i]];
    f1[i] = pw[c1[i]];
    Add(f0[i] - f1[i], +1);
  }
  vector<int> sz(n, 1);
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int a, b;
      cin >> a >> b;
      --a; --b;
      if (d.get(a) == d.get(b)) {
        swap(c0[a], c0[b]);
        continue;
      }
      int na = a;
      int nb = b;  
      a = d.get(a);
      b = d.get(b);
      Remove(f0[a] - f1[a], sz[a]);
      Remove(f0[b] - f1[b], sz[b]);
      f0[a] -= pw[c0[a]];
      f0[a] += pw[c0[b]];
      f0[b] -= pw[c0[b]];
      f0[b] += pw[c0[a]];
      Add(f0[a] - f1[a], sz[a]);
      Add(f0[b] - f1[b], sz[b]); 
      swap(c0[na], c0[nb]);
    } else if (op == 2) {
      int a, b;
      cin >> a >> b;
      --a; --b; 
      a = d.get(a);
      b = d.get(b);
      if (a == b) {
        continue;
      }
      Remove(f0[a] - f1[a], sz[a]);
      Remove(f0[b] - f1[b], sz[b]);
      d.unite(a, b);
      if (d.get(a) != a) {
        assert(b == d.get(a));
        swap(a, b);
      }
      f0[a] += f0[b];
      f1[a] += f1[b];
      sz[a] += sz[b];
      Add(f0[a] - f1[a], sz[a]);
    } else if (op == 3) {
      cout << (cnt[0] == n ? "DA" : "NE") << '\n';
    } else {
      cout << ans << '\n';
    }
  }
  return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 4852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1066 ms 43884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1785 ms 85860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 884 ms 50576 KB Output isn't correct
2 Halted 0 ms 0 KB -