Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- #include <map>
- #include <stack>
- #include <cmath>
- #include <set>
- #include <utility>
- #include <iomanip>
- #include <cstdlib>
- #include <ctime>
- #include <list>
- #include <numeric>
- #include <unordered_map>
- using namespace std;
- int main() {
- freopen("input.txt", "r", stdin);
- //freopen("e.out", "w", stdout);
- int n, k;
- cin >> n >> k;
- long long a, b;
- vector<long long> vv(n+1);
- vector<long long> vv1(n+1);
- long long t = 941;
- long long t1 = 757;
- vector<long long> tt(n+1);
- vector<long long> tt1(n+1);
- long long m = 1817814218137;
- long long m1 = 8132721212411;
- tt[0]=1;
- tt1[0]=1;
- for (int i = 0; i < n; ++i) {
- tt[i+1]=(tt[i]*t)%m;
- tt1[i+1]=(tt1[i]*t1)%m1;
- }
- for (long long i = 0 ; i < k; ++i) {
- scanf("%lld%lld", &a, &b);
- vv[a]+=(b*tt[b])%m;
- vv[a]%=m;
- vv[b]+=(a*tt[a])%m;
- vv[b]%=m;
- vv1[a]+=(b*tt1[b])%m1;
- vv1[a]%=m1;
- vv1[b]+=(a*tt1[a])%m1;
- vv1[b]%=m1;
- }
- unordered_map<long long, int> mm;
- unordered_map<long long, int> mm1;
- long long ans = 0;
- for (long long i = 1; i <= n; ++i) {
- mm[(vv[i]+(i*tt[i])%m)%m]++;
- mm1[(vv1[i]+(i*tt1[i])%m1)%m1]++;
- ans+=min(mm[(vv[i]+(i*tt[i])%m)%m], mm1[(vv1[i]+(i*tt1[i])%m1)%m1])-1;
- mm[vv[i]]++;
- mm1[vv1[i]]++;
- ans+=min(mm[vv[i]], mm1[vv1[i]])-1;
- }
- cout << ans << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement