#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 4e5 + 10;
set <int> in[MAXN], out_set[MAXN], in_set[MAXN];
set <pair<int, int>> out_edge[MAXN], in_edge[MAXN];
set <int>::iterator it;
set <pair<int, int>>::iterator itt;
int n, m, ptr[MAXN], p[MAXN], sz[MAXN];
ll ans;
void make_set() {
for (int i = 1; i <= n; i++) {
p[i] = i; sz[i] = 1;
in[i].clear(); out_set[i].clear(); in_set[i].clear();
out_edge[i].clear(); in_edge[i].clear();
ptr[i] = i;
}
ans = 0;
}
int getp(int u) {
if (p[u] == u)
return u;
return p[u] = getp(p[u]);
}
void un(int u, int v) {
u = getp(u); v = getp(v);
if (u == v)
return;
if (sz[u] + in_edge[ptr[u]].size() + out_edge[ptr[u]].size() > sz[v] + in_edge[ptr[v]].size() + out_edge[ptr[v]].size())
swap(u, v);
int cu = 0, cv = in_edge[ptr[v]].size();
ans += (ll)sz[u] * (ll)sz[v] * 2ll;
for (itt = out_edge[ptr[u]].begin(); itt != out_edge[ptr[u]].end(); itt++) {
pair<int, int> tmp = *itt;
int fr = tmp.fi, to = tmp.se;
if (getp(to) == v) {
ans -= (ll)sz[v];
cv--;
in_edge[ptr[v]].erase(tmp);
} else {
out_edge[ptr[v]].insert(tmp);
}
}
for (itt = in_edge[ptr[u]].begin(); itt != in_edge[ptr[u]].end(); itt++) {
pair<int, int> tmp = *itt;
int fr = tmp.fi, to = tmp.se;
if (getp(fr) == v) {
ans -= (ll)sz[u];
out_edge[ptr[v]].erase(tmp);
} else {
if (in[ptr[v]].count(fr)) {
cv--;
out_edge[ptr[getp(fr)]].erase(tmp);
} else {
cu++;
in_edge[ptr[v]].insert(tmp);
}
}
}
for (it = in[ptr[u]].begin(); it != in[ptr[u]].end(); it++) {
int fr = *it;
if (getp(fr) != v)
in[ptr[v]].insert(fr);
}
for (itt = out_edge[ptr[u]].begin(); itt != out_edge[ptr[u]].end(); itt++) {
pair<int, int> tmp = *itt;
int fr = tmp.fi, to = tmp.se;
if (getp(to) == v) {
in[ptr[v]].erase(fr);
}
}
ans += (ll)cu * (ll)sz[v] + (ll)cv * (ll)sz[u];
set <pair<int, int>> tocon; tocon.clear();
for (it = in_set[ptr[u]].begin(); it != in_set[ptr[u]].end(); it++) {
int fr = *it;
if (fr == v)
continue;
in_set[ptr[v]].insert(fr);
out_set[ptr[fr]].insert(v);
out_set[ptr[fr]].erase(u);
if (in_set[ptr[fr]].count(v))
tocon.insert({v, fr});
}
for (it = out_set[ptr[u]].begin(); it != out_set[ptr[u]].end(); it++) {
int to = *it;
if (to == v)
continue;
out_set[ptr[v]].insert(to);
in_set[ptr[to]].insert(v);
in_set[ptr[to]].erase(u);
if (out_set[ptr[to]].count(v))
tocon.insert({v, to});
}
in[ptr[u]].clear(); in_set[ptr[u]].clear(); out_set[ptr[u]].clear();
in_edge[ptr[u]].clear(); out_edge[ptr[u]].clear();
p[u] = v;
sz[v] += sz[u];
for (itt = tocon.begin(); itt != tocon.end(); itt++) {
pair<int, int> tmp = *itt;
un(tmp.fi, tmp.se);
}
}
void connect(int u, int v) {
int ru = u, rv = v;
u = getp(u); v = getp(v);
if (u == v || in[ptr[v]].count(ru))
return;
ans += (ll)sz[v];
out_edge[ptr[u]].insert({ru, rv});
in_edge[ptr[v]].insert({ru, rv});
in[ptr[v]].insert(ru);
out_set[ptr[u]].insert(v);
in_set[ptr[v]].insert(u);
if (in_set[ptr[u]].count(v))
un(u, v);
}
main() {
// freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &m);
make_set();
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
connect(u, v);
printf("%lld\n", ans);
}
}
Compilation message
joitter2.cpp: In function 'void un(int, int)':
joitter2.cpp:43:9: warning: unused variable 'fr' [-Wunused-variable]
43 | int fr = tmp.fi, to = tmp.se;
| ^~
joitter2.cpp:54:22: warning: unused variable 'to' [-Wunused-variable]
54 | int fr = tmp.fi, to = tmp.se;
| ^~
joitter2.cpp: At global scope:
joitter2.cpp:128:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
128 | main() {
| ^
joitter2.cpp: In function 'int main()':
joitter2.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
130 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
joitter2.cpp:134:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
134 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
94316 KB |
Output is correct |
| 2 |
Correct |
57 ms |
94316 KB |
Output is correct |
| 3 |
Execution timed out |
5067 ms |
94444 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
94316 KB |
Output is correct |
| 2 |
Correct |
57 ms |
94316 KB |
Output is correct |
| 3 |
Execution timed out |
5067 ms |
94444 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
94316 KB |
Output is correct |
| 2 |
Correct |
57 ms |
94316 KB |
Output is correct |
| 3 |
Execution timed out |
5067 ms |
94444 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
