Submission #1060303

#TimeUsernameProblemLanguageResultExecution timeMemory
1060303nima_aryanMaking Friends on Joitter is Fun (JOI20_joitter2)C++17
100 / 100
429 ms49748 KiB
/** * author: NimaAryan * created: 2024-08-15 13:30:23 **/ #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") using namespace std; #ifdef LOCAL #include "algo/debug.h" #endif using i64 = long long; constexpr int N = 1E5; i64 ans = 0; vector<set<int>> S(N); // all vertices in A vector<set<int>> T(N); // {x->a | a \in A} vector<set<int>> G(N); // {B | a \in A, a->B} vector<int> par(N, -1); queue<pair<int, int>> to_merge; int find(int x) { return par[x] == -1 ? x : par[x] = find(par[x]); } int size(int A) { return S[A].size() + T[A].size() + G[A].size(); } void unite(int A, int B) { A = find(A), B = find(B); if (A == B) { return; } if (size(A) < size(B)) { swap(A, B); } ans -= 1LL * S[A].size() * (S[A].size() - 1); ans -= 1LL * S[A].size() * T[A].size(); ans -= 1LL * S[B].size() * (S[B].size() - 1); ans -= 1LL * S[B].size() * T[B].size(); for (int X : G[B]) { if (G[X].count(A)) { to_merge.emplace(A, X); } } T[A].insert(T[B].begin(), T[B].end()); for (int b : S[B]) { T[A].erase(b); } for (int x : T[B]) { int X = find(x); if (X == A) { T[A].erase(x); } else if (G[A].count(X)) { to_merge.emplace(A, X); } if (X != A) { G[X].erase(B); G[X].insert(A); } } S[A].insert(S[B].begin(), S[B].end()); G[A].insert(G[B].begin(), G[B].end()); G[A].erase(B); G[A].erase(A); par[B] = A; ans += 1LL * S[A].size() * (S[A].size() - 1); ans += 1LL * S[A].size() * T[A].size(); S[B].clear(); T[B].clear(); G[B].clear(); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int x = 0; x < n; ++x) { S[x] = {x}; } while (m--) { int a, b; cin >> a >> b; --a, --b; int A = find(a), B = find(b); if (A != B) { if (G[B].count(A)) { unite(A, B); } else if (!T[B].count(a)) { ans += S[B].size(); T[B].insert(a); G[A].insert(B); } while (!to_merge.empty()) { auto [X, Y] = to_merge.front(); to_merge.pop(); unite(X, Y); } } cout << ans << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...