#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 2e5+10;
int n, m;
int cale[maxn], siz[maxn];
llint sol = 0;
set< pair<int, int> > graph[maxn], graph2[maxn];
int fin(int x) {
if (x == cale[x]) return x;
return cale[x] = fin(cale[x]);
}
int get_size(int x) {
return graph[x].size() + graph2[x].size();
}
void remove(int x, set< pair<int, int> > &s, bool flag = false) {
auto iter = s.lower_bound({x, -1});
while (iter != s.end() && iter->X == x) {
//if (flag) printf("removing: %d %d (%d)\n", iter->X, iter->Y, siz[x]);
sol -= siz[x] * flag;
iter = s.erase(iter);
}
}
void replace(int x, int y, set< pair<int, int> > &s, bool flag = false) {
while (true) {
auto iter = s.lower_bound({x, -1});
if (iter == s.end() || iter->X != x) break;
//if (flag) printf("replacing\n");
if (!s.count({y, iter->Y})) {
s.insert({y, iter->Y});
sol += flag * siz[y];
}
s.erase(iter);
sol -= flag * siz[x];
}
}
void merge(int x, int y) {
remove(x, graph[y], true);
remove(y, graph[x], true);
remove(x, graph2[y], false);
remove(y, graph2[x], false);
if (get_size(x) > get_size(y)) swap(x, y);
//printf("merging: %d %d\n", x, y);
cale[x] = y;
sol -= (llint)siz[x] * (siz[x] - 1) + (llint)siz[y] * (siz[y] - 1);
siz[y] += siz[x];
sol += (llint)siz[y] * (siz[y] - 1);
//printf("current: %lld\n", sol);
int nex = -1;
for (auto iter : graph[x]) {
//printf("graph1: %d --> (%d %d)\n", x, iter.X, iter.Y);
int tren = iter.X;
int las = iter.Y;
auto it = graph[tren].lower_bound({y, -1});
if (it != graph[tren].end() && it->X == y) nex = tren;
if (graph[y].count(iter) == 0) sol += siz[x];
graph[y].insert(iter);
sol -= siz[x];
replace(x, y, graph2[tren]);
}
//printf("velicina: %d %d\n", siz[x], graph2[y].size());
sol += (llint)siz[x] * graph2[y].size();
for (auto iter : graph2[x]) {
//printf("graph2: %d --> (%d %d)\n", x, iter.X, iter.Y);
int tren = iter.X;
int las = iter.Y;
auto it = graph2[tren].lower_bound({y, -1});
if (it != graph2[tren].end() && it->X == y) nex = tren;
graph2[y].insert(iter);
replace(x, y, graph[tren], true);
}
//printf("end: %lld\n", sol);
if (nex != -1) merge(y, nex);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
cale[i] = i, siz[i] = 1;
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d%d", &a, &b);
int ca = a, cb = b;
a = fin(a);
b = fin(b);
if (a == b) {
auto iter = graph[b].lower_bound({a, -1});
if (iter == graph[b].end() || iter->X != a) {
if (!graph[a].count({b, ca})) {
graph[a].insert({b, ca});
sol += siz[b];
}
graph2[b].insert({a, 0});
} else merge(a, b);
}
printf("%lld\n", sol);
}
return 0;
}
Compilation message
joitter2.cpp: In function 'void merge(int, int)':
joitter2.cpp:64:7: warning: unused variable 'las' [-Wunused-variable]
64 | int las = iter.Y;
| ^~~
joitter2.cpp:79:7: warning: unused variable 'las' [-Wunused-variable]
79 | int las = iter.Y;
| ^~~
joitter2.cpp: In function 'int main()':
joitter2.cpp:98:15: warning: unused variable 'cb' [-Wunused-variable]
98 | int ca = a, cb = b;
| ^~
joitter2.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
joitter2.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
