Submission #626812

#	Time	Username	Problem	Language	Result	Execution time	Memory
626812		MilosMilutinovic	Zamjene (COCI16_zamjene)	C++14	0 / 140	1773 ms	86100 KiB

zamjene

/**
 *    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;
  }
};

#define int long long

signed 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 long long 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, long long> cnt;
  long long ans = 0;
  auto Add = [&](int x, long long c) {
    if (x != 0) {
      ans += cnt[-x] * 1LL * c;
    }
    cnt[x] += c;
  }; 
  auto Remove = [&](int x, long long 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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14