#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e5 + 5;
const int T = 1000;
multiset <int> in[N], out[N];
vector <int> node[N];
long long ans;
int par[N];
int n,m;
int getpar(int u) {
return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
}
void join(int u, int v) {
u = getpar(u);
v = getpar(v);
if (u == v)
return;
if (in[u].size() + out[u].size() + node[u].size() < in[v].size() + out[v].size() + node[v].size())
swap(u, v);
ans += (long long) 2 * par[u] * par[v];
out[u].erase(v);
for (int x : node[v]) {
if (in[u].count(x)) {
in[u].erase(x);
ans -= (-par[u]);
}
node[u].push_back(x);
}
ans += (long long) in[u].size() * (-par[v]);
vector <int> add;
for (int x : in[v]) {
if (getpar(x) == u)
ans -= (-par[v]);
else if (!in[u].count(x)) {
out[x].erase(out[x].find(v));
out[x].insert(u);
in[u].insert(x);
ans += (-par[u]);
if (out[u].count(getpar(x)))
add.push_back(getpar(x));
}
}
for (int x : out[v])
if (x != u)
out[u].insert(x);
par[u] += par[v];
par[v] = u;
for (int x : add)
join(u, x);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
node[i].push_back(i);
par[i] = -1;
}
for (int i = 1; i <= m; i++) {
int u,v;
cin >> u >> v;
int pu = getpar(u);
int pv = getpar(v);
if (!in[pv].count(u)) {
in[pv].insert(u);
out[pu].insert(pv);
ans += -par[pv];
if (out[pv].count(pu))
join(pu, pv);
}
cout << ans << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
