Submission #963281

#TimeUsernameProblemLanguageResultExecution timeMemory
963281Soumya1Making Friends on Joitter is Fun (JOI20_joitter2)C++17
100 / 100
969 ms81832 KiB
#include <bits/stdc++.h> using namespace std; const int mxN = 1e5 + 5; int sz[mxN], par[mxN]; queue<pair<int, int>> q; set<int> outc[mxN], inc[mxN], inn[mxN]; set<pair<int, int>> outn[mxN]; long long ans; int find(int u) { return (u == par[u] ? u : find(par[u])); } long long contrib(int a) { return 1LL * sz[a] * (sz[a] + inn[a].size() - 1); } void merge(int a, int b) { int aa = find(a), bb = find(b); if (aa == bb) return; if (inn[bb].find(a) != inn[bb].end()) return; if (outc[bb].find(aa) == outc[bb].end()) { ans -= contrib(bb); inc[bb].insert(aa); outc[aa].insert(bb); inn[bb].insert(a); outn[aa].insert({a, bb}); ans += contrib(bb); return; } ans -= contrib(aa) + contrib(bb); if (sz[aa] > sz[bb]) swap(aa, bb), swap(a, b); outc[bb].erase(aa); inc[aa].erase(bb); for (int x : outc[aa]) { inc[x].erase(aa); } for (int x : inc[aa]) { outc[x].erase(aa); } outc[aa].clear(), inc[aa].clear(); for (auto x : inn[aa]) { q.push({x, bb}); outn[find(x)].erase({x, aa}); } for (auto [x, y] : outn[aa]) { q.push({x, y}); if (y != bb) ans -= contrib(y); inn[y].erase(x); if (y != bb) ans += contrib(y); } inn[aa].clear(), outn[aa].clear(); par[aa] = bb; sz[bb] += sz[aa]; ans += contrib(bb); } void testCase() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { sz[i] = 1, par[i] = i; } while (m--) { int a, b; cin >> a >> b; q.push({a, b}); while (!q.empty()) { auto [x, y] = q.front(); q.pop(); merge(x, y); } cout << ans << "\n"; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); testCase(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...