Submission #212162

#TimeUsernameProblemLanguageResultExecution timeMemory
212162achvanovMaking Friends on Joitter is Fun (JOI20_joitter2)C++17
0 / 100
10 ms9728 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, m; long long ans; int p[N]; long long sz[N]; set<int> f[N], g[N]; int get(int v) { return (v == p[v] ? v : p[v] = get(p[v])); } void unite(int u, int v) { u = get(u), v = get(v); if (u == v) { return; } if (f[u].size() + g[u].size() < f[v].size() + g[v].size()) { swap(u, v); } ans -= f[u].size() * sz[u] - sz[u]; ans -= f[v].size() * sz[v] - sz[v]; for (int x : f[v]) { f[u].insert(x); } for (int x : g[v]) { g[u].insert(x); } sz[u] += sz[v]; p[v] = u; ans += f[u].size() * sz[u] - sz[u]; } void connect(int u, int v) { int uu = get(u), vv = get(v); if (uu == vv) { return; } if (f[vv].count(u)) { return; } if (g[uu].count(vv)) { unite(u, v); } else { ans += sz[vv]; f[vv].insert(u); g[vv].insert(uu); } } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m; for (int i = 0; i < n; ++i) { p[i] = i; f[i].insert(i); sz[i] = 1; } while (m--) { int u, v; cin >> u >> v; --u, --v; connect(u, v); cout << ans << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...