#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
ll n,m,p[300004],sz[300005],raod[300005],ans,to;
map<ll,ll>kk[300005],hav[300005],fo;
vector<pair<ll,ll> >in[300005],out[300005];
vector<ll>zz[300005];
pair<ll,ll>too;
ll find(ll x){
if(x == p[x])return x;
return p[x] = find(p[x]);
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=1; i<=n; i++)
p[i] = i,
sz[i] = 1;
while(m--){
ll x,y;
cin >> x >> y;
ll pp = x;
if(kk[x][find(y)]){
cout << ans << '\n';
continue;
}
kk[x][find(y)] = 1;
zz[find(y)].pb(x);
x = find(x);
y = find(y);
if(x == y){
cout << ans <<"\n";
continue;
}
ll k = 0 , ye = 0;
if(in[y].size() + out[y].size() + sz[y] > in[x].size() + out[x].size() + sz[x])k = 1;
ll tt = 0;
fo.clear();
if(k == 0){
for(int i=0; i<out[y].size(); i++){
too = out[y][i];
too.s = find(too.s);
if(too.s == x){ye = 1;if(fo[too.f] == 0)tt -= sz[x]; fo[too.f] = 1;}
}
}
if(k == 1){
for(int i=0; i<in[x].size(); i++){
too = in[x][i];
too.s = find(too.s);
if(too.s == y){if(fo[too.f] == 0)tt -= sz[x]; fo[too.f] = 1; ye = 1;}
}
}
if(ye){
ans += tt + 2 * sz[x] * sz[y];
if(sz[y] + in[y].size() + out[y].size() + zz[y].size() > sz[x] + in[x].size() + out[x].size() + zz[x].size())swap(x , y);
for(int i=0; i<zz[y].size(); i++){
kk[zz[y][i]][x] = 1;
zz[x].pb(zz[y][i]);
}
ll ff = 0;
for(int i=0; i<out[y].size(); i++){
to = out[y][i].s;
to = find(to);
if(to == x)ff = 1;
if(to != x && to != y){
out[x].pb(out[y][i]);
}
}
raod[x] -= ff;
ans += raod[x] * sz[y];
for(int i=0; i<in[y].size(); i++){
to = in[y][i].s;
to = find(to);
if(to != x && to != y){
if(hav[x][to]){
ans -= sz[y];
continue;
}
in[x].pb(in[y][i]);
hav[x][to] = 1;
raod[x]++;
ans += sz[x];
}
}
p[y] = x;
sz[x] += sz[y];
}
else{
in[y].pb(mp(pp,x));
out[x].pb(mp(pp,y));
hav[y][x] = 1;
raod[y]++;
ans += sz[y];
}
cout << ans << '\n';
}
/*
5 10
4 2
1 5
2 3
2 5
3 2
3 1
4 5
1 2
5 2
1 4
*/
return 0;
}
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0; i<out[y].size(); i++){
| ~^~~~~~~~~~~~~~
joitter2.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i=0; i<in[x].size(); i++){
| ~^~~~~~~~~~~~~
joitter2.cpp:62:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i=0; i<zz[y].size(); i++){
| ~^~~~~~~~~~~~~
joitter2.cpp:67:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=0; i<out[y].size(); i++){
| ~^~~~~~~~~~~~~~
joitter2.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=0; i<in[y].size(); i++){
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
49772 KB |
Output is correct |
| 2 |
Correct |
36 ms |
49644 KB |
Output is correct |
| 3 |
Incorrect |
34 ms |
49644 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
49772 KB |
Output is correct |
| 2 |
Correct |
36 ms |
49644 KB |
Output is correct |
| 3 |
Incorrect |
34 ms |
49644 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
49772 KB |
Output is correct |
| 2 |
Correct |
36 ms |
49644 KB |
Output is correct |
| 3 |
Incorrect |
34 ms |
49644 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
