#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include <cmath>
#include <utility>
#include <numeric>
using namespace std;
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
cout << "[";
for (auto it = v.begin(); it != v.end();) {
cout << *it;
if (++it != v.end()) cout << ", ";
}
return cout << "]";
}
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;
#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
//var
ll T;
struct DSU {
int n;
vector<int> par, siz;
vector<set<int>> outgoing, incoming, hitting;
vector<pii> to_onion;
ll running_ans = 0;
// inductively assuming it's up to date already
// choose smallest outgoing + incoming size?
// insert all incoming that aint from big boy into big boy
// change all outgoing to new big boy
// delete outgoing if it goes into big boy
DSU (int n) : n(n), par(n), siz(n, 1), outgoing(n), incoming(n), hitting(n), running_ans(0) {
iota(all(par), 0);
};
int fnd(int g) {
if (g == par[g]) return g;
return par[g] = fnd(par[g]);
}
void one_way(int a, int b) {
assert (a == fnd(a) and b == fnd(b));
outgoing[a].insert(b);
incoming[b].insert(a);
if (incoming[a].count(b)) {
to_onion.pb({a, b});
}
}
void onion(int a, int b) {
a = fnd(a), b = fnd(b);
if (a == b) return;
int sa = (int)outgoing[a].size() + (int)incoming[a].size() + (ll)hitting[a].size();
int sb = (int)outgoing[b].size() + (int)incoming[b].size() + (ll)hitting[b].size();
if (sa > sb) {
swap(a, b);
swap(sa, sb);
}
auto C2 = [&](ll x) -> ll {
return ((x) * (x - 1));
};
running_ans -= (ll)siz[a] * (ll)hitting[a].size();
running_ans -= (ll)siz[b] * (ll)hitting[b].size();
for (auto u : hitting[a]) {
assert(fnd(u) != a);
if (fnd(u) != b) {
hitting[b].insert(u);
}
}
running_ans -= C2(siz[a]) + C2(siz[b]);
for (auto u : incoming[a]) {
outgoing[u].erase(a);
if (fnd(u) != b and fnd(u) != a) {
one_way(u, b);
}
}
for (auto u : outgoing[a]) {
incoming[u].erase(a);
if (fnd(u) != b and fnd(u) != a) {
one_way(b, u);
}
}
incoming[b].erase(a);
outgoing[b].erase(a);
incoming[a].erase(b);
outgoing[a].erase(b);
hitting[a].erase(b);
hitting[b].erase(a);
par[a] = b;
siz[b] += siz[a];
running_ans += (ll)siz[b] * (ll)hitting[b].size();
running_ans += C2(siz[b]);
incoming[a].clear();
outgoing[a].clear();
hitting[a].clear();
}
void add_edge(int a, int b) {
b = fnd(b);
if (fnd(a) == fnd(b)) return;
running_ans -= (ll)siz[b] * (ll)hitting[b].size();
hitting[b].insert(a);
running_ans += (ll)siz[b] * (ll)hitting[b].size();
a = fnd(a);
one_way(a, b);
while (!to_onion.empty()) {
auto [x, y] = to_onion.back();
to_onion.pop_back();
onion(x, y);
}
}
};
void solve() {
int n, m;
cin >> n >> m;
DSU dsu(n);
while (m--) {
ll x, y;
cin >> x >> y;
x--; y--;
dsu.add_edge(x, y);
#ifdef LOCAL
cout << "answer: ";
#endif
cout << dsu.running_ans << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
T = 1;
//cin >> T;
FOR(t, T)
solve();
cout.flush();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
