This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |