#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#ifdef LOCAL
#include "algo/debug.h"
#endif
#define f first
#define s second
template<class T> using V = vector<T>;
using vi = V<int>;
using vb = V<bool>;
using vs = V<string>;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>& a, const T& b) { return lb(all(a),b)-bg(a); }
template<class T> int upb(V<T>& a, const T& b) { return ub(all(a),b)-bg(a); }
int n, m;
queue<array<int, 2>> to_merge;
const int max_n = 1e5;
set<int> child[max_n], g[max_n], gr[max_n];
int sz[max_n], par[max_n], ans = 0;
int find(int u) {
return par[u] == u ? u : par[u]=find(par[u]);
}
int dsu_size(int U) {
return child[U].size() + g[U].size() + gr[U].size();
}
void weak_connect(int U, int V) {
g[U].insert(V); gr[V].insert(U);
if (g[V].count(U)) {
to_merge.push({U, V});
}
}
void onion(int U, int V) {
if (U == V) return;
if (dsu_size(U) < dsu_size(V)) swap(U, V);
ans += sz[U]*child[V].size() + sz[V]*child[U].size();
par[V] = U;
sz[U] += sz[V];
for (auto c : child[V]) {
if (child[V].count(c)) ans -= sz[U];
else child[U].insert(c);
}
g[U].erase(V); g[V].erase(U);
gr[U].erase(V); gr[V].erase(U);
for (auto u : g[V]) {
gr[V].erase(u);
weak_connect(u, V);
}
for (auto u : gr[V]) {
g[u].erase(V);
weak_connect(V, u);
}
}
void solve() {
cin >> n >> m;
for (int i = 0; i < n; i++) par[i] = i, sz[i]=1;
while (m--) {
int u, v; cin >> u >> v; u--; v--;
int U = find(u), V = find(v);
if (U == V) continue;
if (!child[V].count(u)) {
child[V].insert(u);
ans += sz[V];
weak_connect(U, V);
while (to_merge.size()) {
onion(find(to_merge.back()[0]), find(to_merge.back()[1]));
to_merge.pop();
}
}
cout << ans << '\n';
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
15860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
15860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
15860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
