#include <iostream>
#include <vector>
#include <map>
#include <vector>
#include <array>
#include <queue>
#define ll long long
using namespace std;
vector <ll> V[100000];
queue <array<ll, 2>> Q;
map <ll, ll> adj[100000], radj[100000], cyc[100000], rcyc[100000];
ll n, m, a, b, f, P[100000], sz[100000];
ll dsu(ll u) {
if (P[u] == u) return u;
else return P[u] = dsu(P[u]);
}
void merge(ll a, ll b) {
a = dsu(a), b = dsu(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
for (auto [x, y] : cyc[b]) {
if (x == a) continue;
++cyc[a][x];
++rcyc[x][a];
if (cyc[x].count(a)) Q.push({x, a});
}
for (auto [x, y] : rcyc[b]) {
if (x == a) continue;
++rcyc[a][x];
++cyc[x][a];
if (cyc[a].count(x)) Q.push({x, a});
}
cyc[a].erase(b);
rcyc[a].erase(b);
cyc[b].clear();
rcyc[b].clear();
for (auto [x, y] : radj[b]) {
if (dsu(x) == a || adj[x].count(a)) f -= sz[b];
else {
++adj[x][a];
++radj[a][x];
f += sz[a];
f -= sz[b];
}
adj[x].erase(b);
}
radj[b].clear();
for (auto u : V[b]) {
if (adj[u].count(a)) {
adj[u].erase(a);
radj[a].erase(u);
f -= sz[a];
}
V[a].push_back(u);
}
V[b].clear();
f += radj[a].size() * sz[b];
f += sz[a] * sz[b] * 2;
sz[a] += sz[b];
P[b] = a;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
cin >> n >> m;
for (int i=0; i<n; ++i) P[i] = i, sz[i] = 1, V[i].push_back(i);
for (int i=0; i<m; ++i) {
cin >> a >> b;
--a, --b;
b = dsu(b);
if (!adj[a].count(b)) {
++adj[a][b];
++radj[b][a];
f += sz[b];
}
a = dsu(a);
if (a == b) {
cout << f << '\n';
continue;
}
++cyc[a][b];
++rcyc[b][a];
if (!cyc[b].count(a)) {
cout << f << '\n';
continue;
}
Q.push({a, b});
while (!Q.empty()) {
auto [x, y] = Q.front();
Q.pop();
merge(x, y);
}
cout << f << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
