Submission #939320

#TimeUsernameProblemLanguageResultExecution timeMemory
939320WonderfulWhaleMaking Friends on Joitter is Fun (JOI20_joitter2)C++17
0 / 100
1 ms4956 KiB
#include<bits/stdc++.h> using namespace std; #define int int64_t #define pb push_back #define pii pair<int, int> #define st first #define nd second #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() const int MAXN = 100'009; int p[MAXN]; int sz[MAXN]; set<int> M[MAXN]; set<pii> S; int Find(int x) { return x==p[x]?x:p[x]=Find(p[x]); } void Union(int a, int b) { p[Find(a)] = Find(b); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; iota(p, p+n+1, 0); for(int i=0;i<m;i++) { int a, b; cin >> a >> b; if(S.count({b, a})==0) { S.insert({a, b}); } else { //cerr << "Merging\n"; Union(a, b); S.erase({b, a}); } int ans = 0; for(int i=1;i<=n;i++) { sz[i] = 0; M[i].clear(); } for(int i=1;i<=n;i++) { sz[Find(i)]++; } for(pii x:S) { M[Find(x.nd)].insert(x.st); } for(int i=1;i<=n;i++) { ans += sz[i]*(sz[i]-1); ans += sz[i]*sz(M[i]); } cout << ans << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...