#include <bits/stdc++.h>
template <class T> using Vec = std::vector<T>;
int scan() {
int x;
std::scanf("%d", &x);
return x;
}
void print(const long long x) {
std::printf("%lld\n", x);
}
struct DSU {
Vec<int> par;
DSU(const int n) : par(n, -1) {}
int find(const int x) {
return par[x] < 0 ? x : par[x] = find(par[x]);
}
int size(const int x) {
return -par[find(x)];
}
void absorb(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
par[x] += par[y];
par[y] = x;
}
}
};
int main() {
const int N = scan();
int M = scan();
Vec<std::map<int, std::set<int>>> in(N), out(N);
DSU dsu(N);
long long answer = 0;
Vec<std::pair<int, int>> merge;
const auto process = [&] {
while (!merge.empty()) {
auto [x, y] = merge.back();
merge.pop_back();
x = dsu.find(x);
y = dsu.find(y);
if (x == y) {
continue;
}
answer += (long long) dsu.size(x) * dsu.size(y) * 2;
for (auto &[z, set] : in[y]) {
if (set.empty() or dsu.find(z)) {
continue;
}
answer -= (long long) set.size() * dsu.size(y);
if (!out[x][z].empty()) {
answer -= (long long) out[x][z].size() * dsu.size(z);
out[x][z].clear();
in[z][x].clear();
set.clear();
out[z][y].clear();
merge.emplace_back(x, z);
} else {
for (const auto u : set) {
out[z][y].erase(u);
if (in[x][z].insert(u).second) {
answer += dsu.size(x);
out[z][x].insert(u);
}
}
set.clear();
}
}
for (const auto &[z, set] : in[x]) {
answer += (long long) dsu.size(y) * set.size();
}
for (auto &[z, set] : out[y]) {
if (set.empty()) {
continue;
}
if (!out[z][x].empty()) {
answer -= (long long) out[z][x].size() * (dsu.size(x) + dsu.size(y));
answer -= (long long) set.size() * dsu.size(z);
out[z][x].clear();
in[x][z].clear();
set.clear();
in[z][y].clear();
merge.emplace_back(x, z);
} else {
for (const auto u : set) {
out[x][z].insert(u);
in[z][x].insert(u);
in[z][y].erase(u);
}
set.clear();
}
}
dsu.absorb(x, y);
}
};
while (M--) {
const int a = scan() - 1;
const int b = scan() - 1;
const int u = dsu.find(a);
const int v = dsu.find(b);
if (u != v) {
if (!in[u][v].empty()) {
answer -= (long long) out[v][u].size() * dsu.size(u);
in[u][v].clear();
out[v][u].clear();
merge.emplace_back(u, v);
process();
} else {
if (out[u][v].insert(a).second) {
in[v][u].insert(a);
answer += dsu.size(v);
}
}
}
print(answer);
// for (int i = 0; i < N; ++i) {
// if (dsu.find(i) == i) {
// std::cout << "group" << i << '\n';
// std::cout << "in: ";
// for (const auto [x, y] : in[i]) {
// std::cout << "(" << x << ", " << y.size() << ") ";
// }
// std::cout << "\n";
// std::cout << "out: ";
// for (const auto [x, y] : out[i]) {
// std::cout << "(" << x << ", " << y.size() << ") ";
// }
// std::cout << "\n";
// }
// }
}
return 0;
}
Compilation message
joitter2.cpp: In function 'int scan()':
joitter2.cpp:7:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
7 | std::scanf("%d", &x);
| ~~~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
