Submission #939314

#TimeUsernameProblemLanguageResultExecution timeMemory
939314WonderfulWhaleMaking Friends on Joitter is Fun (JOI20_joitter2)C++17
0 / 100
2 ms6744 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 cnt[MAXN]; int p[MAXN]; int sz[MAXN]; set<int> M[MAXN]; set<pii> S; int ans; int Find(int x) { return x==p[x]?x:p[x]=Find(p[x]); } void Union(int a, int b) { int A = Find(a), B = Find(b); if(sz(M[A])<sz(M[B])) swap(A, B); ans -= sz[A]*(sz[A]-1); ans -= sz[B]*(sz[B]-1); ans -= sz[A]*sz(M[A]); ans -= sz[B]*sz(M[B]); //cerr << "after deleting: " << ans << "\n"; sz[A] += sz[B]; p[B] = A; for(int x:M[B]) { M[A].insert(x); } M[B].clear(); M[A].erase(a); M[A].erase(b); ans += sz[A]*(sz[A]-1); ans += sz[A]*sz(M[A]); //cerr << "new stats: " << sz[A] << " " << sz(M[A]) << "\n"; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; iota(p, p+n+1, 0); fill(sz, sz+n+1, 1); for(int i=0;i<m;i++) { int a, b; cin >> a >> b; if(S.count({b, a})==0) { //cerr << "adding\n"; int B = Find(b); ans -= sz(M[B])*sz[B]; M[B].insert(a); ans += sz(M[B])*sz[B]; } else { //cerr << "Merging\n"; Union(a, b); } S.insert({a, b}); cout << ans << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...