Submission #653163

#TimeUsernameProblemLanguageResultExecution timeMemory
653163gozoniteZamjene (COCI16_zamjene)C++14
Compilation error
0 ms0 KiB
#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> 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; } }

Compilation message (stderr)

zamjene.cpp: In function 'void gen_hash()':
zamjene.cpp:37:21: error: 'chrono' has not been declared
   37 |     unsigned seed = chrono::system_clock::now().time_since_epoch().count();
      |                     ^~~~~~