Submission #858710

#TimeUsernameProblemLanguageResultExecution timeMemory
858710NeroZeinMaking Friends on Joitter is Fun (JOI20_joitter2)C++17
100 / 100
586 ms64920 KiB
#include "bits/stdc++.h" using namespace std; #ifdef Nero #include "Deb.h" #else #define deb(...) #endif const int N = 1e5 + 5; long long ans; set<int> r[N]; int p[N], sz[N]; set<pair<int, int>> in[N], out[N]; int get(int x) { return p[x] = (p[x] == x ? x : get(p[x])); } void merge(int x, int y) { x = get(x), y = get(y); if (x == y) { return; } auto f = in[x].lower_bound(make_pair(y, 0)); while (f != in[x].end() && f->first == y) { ans -= sz[x]; r[x].erase(f->second); out[y].erase(make_pair(x, f->second)); f = in[x].erase(f); } f = in[y].lower_bound(make_pair(x, 0)); while (f != in[y].end() && f->first == x) { ans -= sz[y]; r[y].erase(f->second); out[x].erase(make_pair(y, f->second)); f = in[y].erase(f); } if (in[x].size() + out[x].size() < in[y].size() + out[y].size()) { swap(x, y); } ans -= (long long) in[x].size() * sz[x]; ans -= (long long) in[y].size() * sz[y]; ans -= (long long) sz[x] * (sz[x] - 1); ans -= (long long) sz[y] * (sz[y] - 1); vector<int> to_merge; for (auto [i, j] : in[y]) { out[i].erase({y, j}); out[i].emplace(x, j); if (!in[x].count({i, j})) { in[x].emplace(i, j); r[x].insert(j); } f = out[x].lower_bound(make_pair(i, 0)); if (f != out[x].end() && f->first == i) { to_merge.push_back(i); } } p[y] = x; sz[x] += sz[y]; ans += (long long) in[x].size() * sz[x]; ans += (long long) sz[x] * (sz[x] - 1); for (auto [i, j] : out[y]) { in[i].erase(make_pair(y, j)); in[i].emplace(x, j); out[x].emplace(i, j); f = in[x].lower_bound(make_pair(i, 0)); if (f != in[x].end() && f->first == i) { to_merge.push_back(i); } } for (int i : to_merge) { merge(x, i); } } void add(int x, int y) { int px = get(x), py = get(y); if (px == py || r[py].count(x)) { return; } ans += sz[py]; r[py].insert(x); in[py].emplace(px, x); out[px].emplace(py, x); auto f = in[px].lower_bound(make_pair(py, 0)); if (f != in[px].end() && f->first == py) { merge(px, py); } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; iota(p + 1, p + 1 + n, 1); fill(sz + 1, sz + 1 + n, 1); for (int i = 0; i < m; ++i) { int x, y; cin >> x >> y; add(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...