#include <bits/stdc++.h>
int main() {
using namespace std;
typedef long long ll;
ios_base::sync_with_stdio(0);
int n, m;
cin >> n >> m;
ll ans = 0;
vector<int> label(n);
iota(label.begin(), label.end(), 0);
vector<int> size(n, 1);
vector<set<int>> in(n);
vector<set<pair<int, int>>> out(n);
function<int(int)> get = [&](int u) -> int {
if (label[u] == u)
return u;
return label[u] = get(label[u]);
};
function<void(int, int)> direct = [&](int u, int v) {
int x = get(u);
int y = get(v);
if (x == y)
return;
auto it = out[y].lower_bound({x, 0});
if (it != out[y].end() && (*it).first == x) {
if (in[x].size() + out[x].size() < in[y].size() + out[y].size())
swap(x, y);
vector<pair<int, int>> vout;
for (auto& e : out[y]) {
ans -= size[e.first];
in[e.first].erase(e.second);
if (e.first != x)
vout.push_back(e);
}
out[y].clear();
ans += 1LL * size[y] * (2 * size[x] + in[x].size() - in[y].size());
vector<int> vin;
for (auto& e : in[y]) {
int j = get(e);
out[j].erase({y, e});
if (j != x)
vin.push_back(e);
}
in[y].clear();
label[y] = x;
size[x] += size[y];
for (int& e : vin)
direct(e, x);
for (auto& e : vout)
direct(e.second, x);
} else if (!in[y].count(u)) {
ans += size[y];
in[y].insert(u);
out[x].insert({y, u});
}
};
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
--u, --v;
direct(u, v);
cout << ans << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
